记录编号	275619	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2016-07-02 17:51:15	内存使用	0.45 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=510;
const int maxm=8010;
const int INF=100000000;
int cnt=1,fir[maxn],nxt[maxm];
int to[maxm],cap[maxm],val[maxm];
void addedge(int a,int b,int c,int v){
	nxt[++cnt]=fir[a];to[cnt]=b;
	cap[cnt]=c;val[cnt]=v;fir[a]=cnt;
}

queue<int>q;
int path[maxn];
int dis[maxn],vis[maxn];
int Spfa(int S,int T){
	for(int i=S+1;i<=T;i++)
		dis[i]=INF;
	q.push(S);vis[S]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();vis[x]=0;
		for(int i=fir[x];i;i=nxt[i])
			if(cap[i]&&dis[to[i]]>dis[x]+val[i]){
				dis[to[i]]=dis[x]+val[i];
				if(!vis[to[i]])q.push(to[i]);
				vis[to[i]]=1;path[to[i]]=i;
			}
	}
	return dis[T]==INF?0:dis[T];
}

int Aug(int S,int T){
	int f=INF,p=T;
	while(p!=S){
		f=min(f,cap[path[p]]);
		p=to[path[p]^1];
	}
	p=T;
	while(p!=S){
		cap[path[p]]-=f;
		cap[path[p]^1]+=f;
		p=to[path[p]^1];
	}
	return f;
}

int MCMF(int S,int T){
	int ret=0,d;
	while(d=Spfa(S,T))
		ret+=Aug(S,T)*d;
	return ret;
}

int need[maxn],S,T;
int n,b,f,fc,s,sc;
int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&n);S=0;T=n*2+1;
	for(int i=1;i<=n;i++)
		scanf("%d",&need[i]);
	scanf("%d%d%d%d%d",&b,&f,&fc,&s,&sc);
	
	for(int i=1;i<=n;i++){
		addedge(S,i,need[i],0);
		addedge(i,S,0,0);
		addedge(S,i+n,INF,b);
		addedge(i+n,S,0,-b);
		addedge(i+n,T,need[i],0);
		addedge(T,i+n,0,0);
		if(i+f<=n){
			addedge(i,i+f+n,INF,fc);
			addedge(i+f+n,i,0,-fc);
		}
		if(i+s<=n){
			addedge(i,i+s+n,INF,sc);
			addedge(i+s+n,i,0,-sc);
		}
		if(i!=n){
			addedge(i,i+1,INF,0);
			addedge(i+1,i,0,0);
		}
	}	
	printf("%d\n",MCMF(S,T));
	return 0;
}