【题目描述】
一个餐厅在相继的 n 天里，每天需用的餐巾数不尽相同。假设第 i天需要 ri 块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为 P 分；或者把旧餐巾送到快洗部，洗一块需 M 天，其费用为 F 分；或者送到慢洗部，洗一块需 N 天，其费用为 S 分（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
【备注】
1<=n<=1000
【题目分析】
网络流的关键依然在建图上，此题建图非常巧妙：
1.首先将每一天拆为两个点，增加S,T两个源汇点。
2.由S向每一天连一条容量为ri，费用为0的边，最后最大流即各边之和，每一天的拆的点向T连一条容量为ri，费用为0的边。
3.由S向每一天所拆点连一条容量为INF，费用为P的边，表示每天购买的餐巾数。
4.由第i天向第i+1天（i<n）连一条容量为INF，费用为0的边，表示延迟送洗的餐巾。
5.由第i天向第i+M天（i+M<=n）所拆点连一条容量为INF，费用为F的边，表示送快洗部洗的餐巾。
6.由第i天向第i+N天（i+N<=n）所拆点连一条容量为INF，费用为S的边，表示送慢洗部洗的餐巾。
7.最后在图上跑一遍最小费用最大流即可，答案即为最小费用。
【代码~】
#includeusing namespace std;const int MAXN=2e3+10;const int MAXM=1e5+10;const int INF=0x3f3f3f3f;int n,m,s,t,cnt,cost;int head[MAXN],dis[MAXN],vis[MAXN],work[MAXN];int nxt[MAXN],to[MAXN],w[MAXN],c[MAXN];queue q;void Add(int u,int v,int f,int p){ nxt[cnt]=head[u]; head[u]=cnt; to[cnt]=v; w[cnt]=f; c[cnt]=p; cnt++;}void add(int u,int v,int f,int p){ Add(u,v,f,p); Add(v,u,0,-p);}bool SPFA(){ while(!q.empty()) q.pop(); memset(dis,INF,sizeof(dis)); memset(work,0,sizeof(work)); dis[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(dis[v]>dis[u]+c[i]&&w[i]) { dis[v]=dis[u]+c[i]; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[t]