记录编号	34714	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2011-12-31 11:17:36	内存使用	0.38 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<deque>

using namespace std;

const int oo=~0u>>1;

struct type
{
	int t,w,cost;
	type *next,*back;
	type(int _t,int _w,int _cost,type *_next):t(_t),w(_w),cost(_cost),next(_next){}
}*Map[10010];

int n,p,fw,sw,fc,sc,s,t,ans,r[10010],pre[10010];

void addedge(int v,int t,int w,int cost)
{
	Map[v]=new type(t,w,cost,Map[v]);
	Map[t]=new type(v,0,-cost,Map[t]);
	Map[v]->back=Map[t];
	Map[t]->back=Map[v];
}

void minCmaxF()
{
	deque<int>deq;
	int i,j,dist[10010],u,maxflow;
	bool v[10010];
	type *k,*path[10010];
	for(;;)
	{
		memset(v,false,sizeof(v));
		for(i=1;i<=10000;i++)
			dist[i]=oo;
		dist[s]=0;
		deq.push_back(s);
		while(!deq.empty())
		{
			u=deq.front();
			deq.pop_front();
			v[u]=false;
			for(k=Map[u];k;k=k->next)
			{
				j=k->t;
				if(dist[j]>dist[u]+k->cost&&k->w>0)
				{
					dist[j]=dist[u]+k->cost;
					pre[j]=u;
					path[j]=k;
					if(!v[j])
					{
						v[j]=true;
						if(dist[j]>dist[u])
							deq.push_back(j);
						else
							deq.push_front(j);
					}
				}
			}
		}
		if(dist[t]==oo)
		{
			printf("%d\n",ans);
			return;
		}
		maxflow=oo;
		i=t;
		while(i!=s)
		{
			k=path[i];
			maxflow=min(k->w,maxflow);
			i=pre[i];
		}
		i=t;
		while(i!=s)
		{
			k=path[i];
			k->w-=maxflow;
			k->back->w+=maxflow;
			i=pre[i];
		}
		ans+=dist[t]*maxflow;
	}
}

int main()
{
	int i;
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&r[i]);
	scanf("%d%d%d%d%d",&p,&fw,&fc,&sw,&sc);
	s=n*2+1;
	t=s+1;
	for(i=1;i<=n;i++)
	{
		addedge(s,i,r[i],0);
		addedge(n+i,t,r[i],0);
		addedge(s,n+i,oo,p);
		if(i<n)
			addedge(i,i+1,oo,0);
		if(i+fw<=n)
			addedge(i,i+fw+n,oo,fc);
		if(i+sw<=n)
			addedge(i,i+sw+n,oo,sc);
	}
	minCmaxF();
	return 0;
}