[网络流24题] 餐巾
【问题描述】
一个餐厅在相继的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
这道题建模很巧妙。
只要表示出两类决策就可以了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 const int maxn=510; 7 const int maxm=8010; 8 const int INF=100000000; 9 int cnt=1,fir[maxn],nxt[maxm]; 10 int to[maxm],cap[maxm],val[maxm]; 11 void addedge(int a,int b,int c,int v){ 12 nxt[++cnt]=fir[a];to[cnt]=b; 13 cap[cnt]=c;val[cnt]=v;fir[a]=cnt; 14 } 15 16 queue<int>q; 17 int path[maxn]; 18 int dis[maxn],vis[maxn]; 19 int Spfa(int S,int T){ 20 for(int i=S+1;i<=T;i++) 21 dis[i]=INF; 22 q.push(S);vis[S]=1; 23 while(!q.empty()){ 24 int x=q.front(); 25 q.pop();vis[x]=0; 26 for(int i=fir[x];i;i=nxt[i]) 27 if(cap[i]&&dis[to[i]]>dis[x]+val[i]){ 28 dis[to[i]]=dis[x]+val[i]; 29 if(!vis[to[i]])q.push(to[i]); 30 vis[to[i]]=1;path[to[i]]=i; 31 } 32 } 33 return dis[T]==INF?0:dis[T]; 34 } 35 36 int Aug(int S,int T){ 37 int f=INF,p=T; 38 while(p!=S){ 39 f=min(f,cap[path[p]]); 40 p=to[path[p]^1]; 41 } 42 p=T; 43 while(p!=S){ 44 cap[path[p]]-=f; 45 cap[path[p]^1]+=f; 46 p=to[path[p]^1]; 47 } 48 return f; 49 } 50 51 int MCMF(int S,int T){ 52 int ret=0,d; 53 while(d=Spfa(S,T)) 54 ret+=Aug(S,T)*d; 55 return ret; 56 } 57 58 int need[maxn],S,T; 59 int n,b,f,fc,s,sc; 60 int main(){ 61 freopen("napkin.in","r",stdin); 62 freopen("napkin.out","w",stdout); 63 scanf("%d",&n);S=0;T=n*2+1; 64 for(int i=1;i<=n;i++) 65 scanf("%d",&need[i]); 66 scanf("%d%d%d%d%d",&b,&f,&fc,&s,&sc); 67 68 for(int i=1;i<=n;i++){ 69 addedge(S,i,need[i],0); 70 addedge(i,S,0,0); 71 addedge(S,i+n,INF,b); 72 addedge(i+n,S,0,-b); 73 addedge(i+n,T,need[i],0); 74 addedge(T,i+n,0,0); 75 if(i+f<=n){ 76 addedge(i,i+f+n,INF,fc); 77 addedge(i+f+n,i,0,-fc); 78 } 79 if(i+s<=n){ 80 addedge(i,i+s+n,INF,sc); 81 addedge(i+s+n,i,0,-sc); 82 } 83 if(i!=n){ 84 addedge(i,i+1,INF,0); 85 addedge(i+1,i,0,0); 86 } 87 } 88 printf("%d ",MCMF(S,T)); 89 return 0; 90 }