题目描述
一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。
输入
文件第1 行有6 个正整数N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n是慢洗部洗一块餐巾需用天数；s是慢洗部洗一块餐巾需要的费用。
接下来的N 行是餐厅在相继的N 天里，每天需用的餐巾数。
输出
输出仅有一个整数，为餐厅在相继的N 天里使用餐巾的最小总花费。
样例输入
3 10 2 3 3 2
5
6
7 样例输出
145
费用流。但是如何建图呢。把每天拆成两个点，i为每天有的干净餐巾数，i+N为每天有的脏餐巾数，建一个超级源点S，一个超级汇点T
把S向i连一条容量为INF，费用为p的边。表示每天可以买无限块餐巾，一条餐巾p分
把i向T连一条容量为ri，费用为0的边。表示每天需要ri块餐巾 把S向i+N连一条容量为ri，费用为0的边。表示每天会用脏ri块餐巾 把i+N向i+m连一条容量为INF，费用为f的边。表示每天可以去快洗部清洗无限块餐巾，耗时m天，一条餐巾需f分 把i+N向i+n连一条容量为INF，费用为s的边。表示每天可以去慢洗部清洗无限块餐巾，耗时n天，一条餐巾需s分 把i+N向i+N+1连一条容量为INF，费用为0的边。表示每天可以把未清洗的餐巾留到下一天
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int inq[100000],d[100000],h[100000],q[200000],from[100000],head,tail,k=1,INF=999999999,ans=0,r[100000]; struct data{ int to,cap,cost,next; }g[5000000]; void add(int from,int to,int cap,int cost) { g[++k].next=h[from];h[from]=k;g[k].to=to;g[k].cap=cap;g[k].cost=cost; g[++k].next=h[to];h[to]=k;g[k].to=from;g[k].cap=0;g[k].cost=-cost; } bool spfa(int s,int t) { memset(inq,0,sizeof(inq)); memset(d,127/3,sizeof(d));INF=d[0]; d[s]=0;inq[s]=1;head=tail=100000;q[tail++]=s; while(head<=tail) { int u=q[head++];inq[u]=0; for(int i=h[u];i;i=g[i].next) { if(g[i].cap&&d[u]+g[i].cost<d[g[i].to]) { d[g[i].to]=d[u]+g[i].cost;from[g[i].to]=i; if(!inq[g[i].to]) { if(d[g[i].to]<d[q[head]])q[--head]=g[i].to; else q[tail++]=g[i].to;inq[g[i].to]=1; } } } } if(d[t]==INF)return false; return true; } void mcf(int t) { int minn=INF; for(int i=from[t];i;i=from[g[i^1].to])minn=min(minn,g[i].cap); for(int i=from[t];i;i=from[g[i^1].to])g[i].cap-=minn,g[i^1].cap+=minn,ans+=minn*g[i].cost; } int main() { int N,p,m,f,n,s;scanf("%d%d%d%d%d%d",&N,&p,&m,&f,&n,&s); for(int i=1;i<=N;i++) { scanf("%d",&r[i]); add(2*N+1,i,INF,p);add(i,2*N+2,r[i],0);add(2*N+1,i+N,r[i],0); if(i+m<=N)add(i+N,i+m,INF,f); if(i+n<=N)add(i+N,i+n,INF,s); if(i+1<=N)add(i+N,i+N+1,INF,0); } while(spfa(2*N+1,2*N+2))mcf(2*N+2); printf("%d",ans);return 0; }