«问题描述：
一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，
2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，
洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多
少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。
«编程任务：
编程找出一个最佳餐巾使用计划.
«数据输入：
由文件input.txt提供输入数据。文件第1 行有6 个正整数N,p,m,f,n,s。N 是要安排餐巾
使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗
一块餐巾需要的费用；n是慢洗部洗一块餐巾需用天数；s是慢洗部洗一块餐巾需要的费用。
接下来的N 行是餐厅在相继的N 天里，每天需用的餐巾数。
«结果输出:
程序运行结束时，将餐厅在相继的N 天里使用餐巾的最小总花费输出到文件output.txt
中。
建立源点S汇点T，并把每一天拆分为入点与出点，
以ai表示第i天需要的餐巾数量
S向每天的入点连一条容量ai，费用0的边表示新产生的脏餐巾数
每天的入点向下一天的入点连一条容量无限大，费用0的边表示转移到下一天的脏餐巾
每天的入点向m天后的出点连一条容量无限大，费用f的边表示送去快洗部洗餐巾
每天的入点向n天后的出点连一条容量无限大，费用s的边表示送去慢洗部洗餐巾
每天的出点向T连一条容量ai，费用0的边表示当天需要的干净餐巾
zwk费用流的实现细节解释在代码注释中
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int MAXN=5010000; const int maxn=5010; const int INF=~0U>>1; long long int maxflow=0,cost=0; int v[maxn],dis[maxn]; int r[maxn]; int S,T; int N,p,m,f,n,s; int tot=0; int pointer[maxn]; struct Edge { int to,next,cap,op,f,w; Edge() {}; Edge(int b,int c,int nxt,int num,int flow,int weight) {to=b,cap=c,next=nxt,op=num^1,f=flow,w=weight;} }edge[MAXN]; inline void addedge(int a,int b,int c,int w1) { edge[tot]=Edge(b,c,pointer[a],tot,0,w1); pointer[a]=tot++; edge[tot]=Edge(a,0,pointer[b],tot,0,-w1); pointer[b]=tot++; } inline int aug(int x,int flow) //dfs搜增光路 flow代表当前dfs路径中剩余容量最小边的容量 { if(x==T) { maxflow+=flow; cost+=dis[S]*flow; return flow; } v[x]=1; int l=flow; for(int j=pointer[x];j!=-1;j=edge[j].next) { int y=edge[j].to; if(!v[y]&&edge[j].cap-edge[j].f&&dis[y]+edge[j].w==dis[x]) //距离标号满足要求代表走的这一步是目前情况下到达y的最短路其中的一步 { int tmp=aug(y,min(l,edge[j].cap-edge[j].f)); // edge[j].f+=tmp,edge[j^1].f-=tmp,l-=tmp; //x-->y这条路分走了tmp大小的流量 if(!l) return flow; //到达x点的flow大小的流量被分完了就不必考虑x的其他子节点了 } } return flow-l; } inline bool modlabel() { int minh=INF; rep(i,S,T) { if(v[i]) for(int j=pointer[i];j!=-1;j=edge[j].next) { int y=edge[j].to; if(edge[j].cap-edge[j].f>0&&!v[y]) { minh=min(minh,dis[y]+edge[j].w-dis[i]); } } } if(minh==INF) return 0; rep(i,S,T) if(v[i]) dis[i]+=minh; //利用距离标号控制最短路条件 return 1; } inline void zwk() { do { do { rep(i,S,T) v[i]=0; }while(aug(S,INF)); }while(modlabel()); } inline void init() { memset(pointer,-1,sizeof(pointer)); scanf("%d%d%d%d%d%d",&N,&p,&m,&f,&n,&s); S=0;T=2*N+1; int ri; rep(i,1,N) { scanf("%d",&ri); addedge(S,i,ri,0); addedge(N+i,T,ri,0); addedge(S,N+i,INF,p); if(i+m<=N) addedge(i,N+i+m,INF,f); if(i+n<=N) addedge(i,N+i+n,INF,s); if(i<N) addedge(i,i+1,INF,0); } } int main() { freopen("napk10.in","r",stdin); init(); zwk(); printf("%lld ",cost); return 0; }