【问题描述】
一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。
(1)购买新的餐巾，每块需p分；
(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
(3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<f)。
在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。
【输入】
输入文件共 3 行，第 1 行为总天数；第 2 行为每天所需的餐巾块数；第 3 行为每块餐巾的新购费用 p ，快洗所需天数 m ，快洗所需费用 f ，慢洗所需天数 n ，慢洗所需费用 s 。
【输出】
一行，最小的费用
【样例】
napkin.in
3
3 2 4
10 1 6 2 3
napkin.out
64
【数据规模】
n<=200,Ri<=50
【时空限制】
5s，128MB
【题解】
第一道比较有难度的最小费用最大流，关键是建图。贴lyc学长ppt：
1.每天作为一个点，由S向其连边，容量为Ri。每天向T连边，容量为INF，花费为p，每天都可以购买餐巾无数次
2.将每天用过的餐巾再新建一层点，由于分配去快洗和慢洗的餐巾总数有限制，并非分别有限制，所以这两种无需再分开，这层点分别向T建边，花费为0，容量为Ri，限制总容量。
3.使用快洗的餐巾，由i(需要)向i-m(用过)建边，容量为INF，花费为f；慢洗同理，花费分别建边。
4.第i-m洗完后的餐巾也可以供第i天以后使用，所以再向i+1(需要)向i(需要)建边，容量为INF，花费为0.这样第i天就能使用到以前所有洗完的餐巾了。
这道题真正让我有一种“网络流，流起来”的感觉，像引水一样一步步把可行的答案汇流，最后跑一遍网络流的板子，十分美妙。后来忘了每天建两个点，数组开小，有WA有T。数组开小的危害不仅仅是RE啊。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int sj=410; int d,sy[sj],p,m,f,n,s,sd,hd; int dis[sj],h[sj],e,pre[sj]; bool r[sj]; struct B { int v,ne,w,fl,co; }b[sj*20]; void add(int x,int y,int z,int a) { b[e].v=y; b[e].ne=h[x]; b[e].w=z; b[e].co=a; h[x]=e++; b[e].v=x; b[e].ne=h[y]; b[e].w=0; b[e].co=-a; h[y]=e++; } void init() { scanf("%d",&d); for(int i=1;i<=d;i++) scanf("%d",&sy[i]); memset(h,-1,sizeof(h)); scanf("%d%d%d%d%d",&p,&m,&f,&n,&s); sd=0; hd=d+1; for(int i=1;i<=d;i++) { add(sd,i,sy[i],0); add(i+1,i,0x3fff,0); add(i,hd,0x3fff,p); if(i<d) add(i+d+1,hd,sy[i],0); if(i-m>0) add(i,i-m+d+1,0x3fff,f); if(i-n>0) add(i,i-n+d+1,0x3fff,s); } } queue<int> q; bool spfa() { while(!q.empty()) q.pop(); memset(r,0,sizeof(r)); memset(dis,0x3f,sizeof(dis)); memset(pre,-1,sizeof(pre)); r[sd]=1; dis[sd]=0; q.push(sd); while(!q.empty()) { m=q.front(); q.pop(); r[m]=0; for(int i=h[m];i!=-1;i=b[i].ne) if(dis[b[i].v]>dis[m]+b[i].co&&b[i].w>b[i].fl) { dis[b[i].v]=dis[m]+b[i].co; pre[b[i].v]=i; if(!r[b[i].v]) { q.push(b[i].v); r[b[i].v]=1; } } } return pre[hd]!=-1; } int bj(int x,int y) { return x<y?x:y; } int mcmf() { int cost=0; while(spfa()) { int mi=0x7fffffff; for(int i=pre[hd];i!=-1;i=pre[b[i^1].v]) mi=bj(mi,b[i].w-b[i].fl); for(int i=pre[hd];i!=-1;i=pre[b[i^1].v]) { b[i].fl+=mi; b[i^1].fl-=mi; cost+=mi*b[i].co; } } return cost; } int main() { init(); printf("%d",mcmf()); return 0; }