1 条题解

  • 1
    @ 2022-8-31 9:51:52
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #define ano ((i-1)^1)+1
    using namespace std;
    const int INF=0x7f7f7f7f,N=2e3+100,M=6e3+100;
    int n,a,b,f,fa,fb,tot,ans,s,t;
    int head[N],ver[2*M],edge[2*M],Next[2*M],cost[2*M];
    int pre[N],minf[N],d[N];
    bool v[N];
    void add(int x,int y,int z,int c)
    {
    	ver[++tot]=y,edge[tot]=z,cost[tot]=c,Next[tot]=head[x],head[x]=tot;
    	ver[++tot]=x,edge[tot]=0,cost[tot]=-c,Next[tot]=head[y],head[y]=tot;
    }//网络流双向建边
    bool spfa()
    {
    	memset(v,0,sizeof(v));
    	memset(d,0x7f,sizeof(d));
    	queue<int> q;
    	d[s]=0,v[s]=1,minf[s]=INF;
    	q.push(s);
    	while(q.size())
    	{
    		int x=q.front();q.pop();v[x]=0;
    		for(int i=head[x];i;i=Next[i])
    			if(edge[i])
    			{
    				int y=ver[i];
    				if(d[x]+cost[i]<d[y])
    				{
    					d[y]=d[x]+cost[i];
    					minf[y]=min(minf[x],edge[i]);
    					pre[y]=i;
    					if(!v[y])
    					{
    						q.push(y);
    						v[y]=1;
    					}
    				}
    			}
    	}
    	return d[t]!=INF;
    }
    void update()
    {
    	int x=t;
    	while(x!=s)
    	{
    		int i=pre[x];
    		edge[i]-=minf[t];
    		edge[ano]+=minf[t];
    		x=ver[ano];
    	}
    	ans+=d[t]*minf[t];
    }//最小费用最大流模板
    int main()
    {
    	scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
    	t=2*n+1,a++,b++;//也可以先将a,b分别加1,后面就不用加1
    	for(int i=1;i<=n;i++)
    	{
    		int x;
    		scanf("%d",&x);
    		add(s,i+n,x,0),add(i,t,x,0),add(s,i,INF,f);//1,2,3操作
    		if(i+a<=n)
    			add(i+n,i+a,INF,fa);//4操作
    		if(i+b<=n)
    			add(i+n,i+b,INF,fb);//5操作
    		if(i+1<=n)
    			add(i,i+1,INF,0);//6操作,这里是从每天早上向第二天早上连边
    	}
    	while(spfa())
    		update();//跑最小费用最大流。
    	printf("%d",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    1179
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    2
    已通过
    2
    上传者