餐巾计划问题

题目链接
将每个点拆成白天和晚上,白天只收干净的餐巾,晚上只收脏餐巾,从源点往每天晚上连容量为x,费用为0的边,表示每天晚上会收到x条脏餐巾。
从每天早上往汇点连容量为x,费用为0的边,流满表示餐巾够用。
从每天晚上往下一天晚上连容量inf,费用0的边,表示留到下一天。
从每天晚上往快洗结束的那天早上连容量inf,费用快洗的边,表示快洗。
从每天晚上往慢洗结束的那天早上连容量inf,费用慢洗的边,表示慢洗。
从源点往每天早上连容量inf,费用买新餐巾的边,表示买餐巾
求最小费用最大流即可。

#include <bits/stdc++.h>
typedef long long ll;
const int N=10005,M=100005;
const ll inf=1e16;
int n,m;
ll ans,tmp,tot;
ll u[M],v[M],nxt[M],t=1,S,T,l,r,q[M],g[N],f[N];bool in[N];
ll c[M],co[M],d[N];
void add(int x,int y,ll z,ll zo){
    u[++t]=x;v[t]=y;c[t]=z;co[t]=zo;nxt[t]=g[x];g[x]=t;
    u[++t]=y;v[t]=x;c[t]=0;co[t]=-zo;nxt[t]=g[y];g[y]=t;
}
bool spfa(){
    int x,i;
    for(i=1;i<=T;i++)d[i]=inf,in[i]=0;//注意对所有点进行初始化
    d[S]=0;in[S]=1;l=r=M>>1;q[l]=S;
    while(l<=r){
        int x=q[l++];
        if(x==T)continue;
        for(i=g[x];i;i=nxt[i])if(c[i]&&co[i]+d[x]<d[v[i]]){
            d[v[i]]=co[i]+d[x];f[v[i]]=i;
            if(!in[v[i]]){
                in[v[i]]=1;
                if(d[v[i]]<d[q[l]])q[--l]=v[i];else q[++r]=v[i];
            }
        }
        in[x]=0;
    }
    return d[T]<inf;//最小费用流 d[T]为负继续  最小费用最大流 d[T]不为inf继续
}
ll flow(){
    int i;
    while(spfa()){
        for(tmp=inf,i=T;i!=S;i=u[f[i]])if(tmp>c[f[i]])tmp=c[f[i]];
        for(ans+=d[i=T]*tmp,tot+=tmp;i!=S;i=u[f[i]])c[f[i]]-=tmp,c[f[i]^1]+=tmp;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    S=n*2+1;
    T=n*2+2;
    for(int i=1;i<=n;i++){
    	int x;
    	scanf("%d",&x);
    	add(S,i*2,x,0);
    	add(i*2-1,T,x,0);
    	if(i!=n){
    		add(i*2,i*2+2,inf,0);
    	}
    }
    int P,M,F,N,s;
    scanf("%d%d%d%d%d",&P,&M,&F,&N,&s);
    for(int i=1;i<=n;i++){
    	add(S,i*2-1,inf,P);
    	if(M+i<=n){
    		add(i*2,(i+M)*2-1,inf,F);
    	}
    	if(N+i<=n){
    		add(i*2,(i+N)*2-1,inf,s);
    	}
    }
    flow();
    printf("%lld\n",ans);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注