记录编号	361028	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2017-01-02 19:06:33	内存使用	4.98 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
struct edge{
	int f,t,g,l,o;
	edge(int F=0,int T=0,int G=0,int L=0,int O=0){
		f=F;t=T;g=G;l=L;o=O;
	}
}w[N];
int n,df,cf,ds,cs,p,a[N],head[N],tail[N],next[N];
void add(int f,int t,int g,int l){
	static int cnt=0;
	++cnt;w[cnt]=edge(f,t,g,l,cnt+1);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=edge(t,f,0,-l,cnt-1);
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
//第i天餐巾的入口为i，出口（即使用过的）为i+n，流量为餐巾的流通。
//第i天消耗的餐巾为a[i]，等价于经过i->i+n的流为a[i] 
//那么该图上的最小费用可行流即答案 
queue<int> Q;
int s,t,S,T,ans,dis[N],flow[N],from[N];
bool inque[N];
bool spfa(){
	for (int i=S;i<=T;i++) dis[i]=1e9;
	dis[S]=0;flow[S]=1e9;
	Q.push(S);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inque[v]=0;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&dis[w[i].t]>dis[v]+w[i].l){
			int u=w[i].t;
			dis[u]=dis[v]+w[i].l;
			from[u]=i;
			flow[u]=min(flow[v],w[i].g);
			if (!inque[u]) inque[u]=1,Q.push(u);
		}
	}
	if (dis[T]==1e9) return 0;
	int df=flow[T];ans+=dis[T]*df;
	for (int i=from[T];i;i=from[w[i].f])
		w[i].g-=df,w[w[i].o].g+=df;
	return 1;
}
int main()
{
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d%d%d%d%d",&p,&df,&cf,&ds,&cs);
	s=n*2+1;t=n*2+2;//原图的源汇点 
	add(t,s,1e9,0);
	S=0;T=n*2+3;//新图的源汇点 
	for (int i=1;i<=n;i++){
		add(s,i,1e9,p);//买餐巾 
		//使用餐巾 
		//add(i,i+n,a[i],0);//原图边 
		add(S,i+n,a[i],0);//新图边 
		add(i,T,a[i],0);
		add(i+n,t,1e9,0);//浪费餐巾 
		if (i+df<=n) add(i+n,i+df,1e9,cf);//快洗 
		if (i+ds<=n) add(i+n,i+ds,1e9,cs);//慢洗 
		if (i<n) add(i,i+1,1e9,0);//留着明天用 
	}
	while (spfa());
	printf("%d\n",ans);
	return 0;
}