记录编号	430357	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.354 s
提交时间	2017-07-29 17:48:31	内存使用	2.20 MiB

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define inf 0x7fffffff
using namespace std;
int p,m,f,n,s,t,ne[405],tot,ans,a;
int w[405][405],c[405][405],map[405][405];
void build_map(){
     for(int i=1;i<=t;i++){
     	 //cas1:每天作为一个点，由S向其连边，容量为Ri，花费为0。
     	 c[0][i]=ne[i],c[i][0]=0;
     	 w[0][i]=0,w[i][0]=0;
     	 //cas2:每天可以向T连边，容量为INF，花费为p，每天都可以购买餐巾无数次。
     	 c[0][i+t]=inf,c[i+t][0]=0;
     	 w[0][i+t]=p,w[i+t][0]=-p;
     	 //cas3:每天用过的餐巾在新建一层点，由于分配去快洗和慢洗的餐巾总数有限制，并非分别有限制，所有这两种无需再分开，这层点分别向T建边，容量为Ri,花费为0，限制总容量。
     	 c[i+t][2*t+1]=ne[i],c[2*t+1][i+t]=0;
     	 w[i+t][2*t+1]=0,w[2*t+1][i+t]=0;
     	 //cas4:但第i-m天洗完后的餐巾也可以供第i天以后使用。所以再由i+1向i建边，容量为INF，花费为0。
     	 if(i<t){
     	 	c[i][i+1]=inf,c[i+1][i]=0;
     	 	w[i][i+1]=0,w[i+1][i]=0;
		 }
		 //cas5:使用快洗的餐巾，由i向(i-m)’建边，容量为INF，花费为f;
		 if(i+m<=t){
		 	c[i][i+m+t]=inf,c[i+m+t][i]=0;
		 	w[i][i+m+t]=f,w[i+m+t][i]=-f;
		 }
     	 //cas6:慢洗同理，花费分别建边。
     	 if(i+n<=t){
     	 	c[i][i+n+t]=inf,c[i+n+t][i]=0;
     	 	w[i][i+n+t]=s,w[i+n+t][i]=-s;
		  }
     }
}	  
queue<int> q;
int dis[405],pre[405]; 
bool flag[405];
void minfee_maxflow(){
	 queue<int> q;
	 while(true){
	 	for(int i=0;i<=2*t+1;i++)
	 	    dis[i]=inf,flag[i]=0;
	    dis[0]=0;
		flag[0]=1;
	    q.push(0);
	    while(!q.empty()){
	    	  int k=q.front();
	    	  q.pop();
	    	  flag[k]=0;
	    	  for(int i=1;i<=2*t+1;i++)
	    	      if(c[k][i]>map[k][i]&&dis[i]>dis[k]+w[k][i]){
	    	         dis[i]=dis[k]+w[k][i];
	    	         pre[i]=k;
	    	         if(!flag[i]){
	    	         	flag[i]=1;
						 q.push(i); 
					 }
				}
		}
		if(dis[t*2+1]==inf) break;
        a=inf;
        for(int i=2*t+1;i!=0;i=pre[i])
            a=min(a,c[pre[i]][i]-map[pre[i]][i]);
        for(int i=2*t+1;i!=0;i=pre[i]){
        	map[pre[i]][i]+=a;
        	map[i][pre[i]]-=a;
		}
        ans+=a*dis[t*2+1]; 
	 } 
}
int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=t;i++) scanf("%d",&ne[i]);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	build_map();
	minfee_maxflow();
	printf("%d",ans);
    return 0;
}