记录编号	28807	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	C++	运行时间	0.705 s
提交时间	2011-10-17 18:33:13	内存使用	1.53 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int oo=99999999;

int i,j,n,ans,p,c1,c2,t1,t2;
int NS,NT,kk;
int u[402],f[402],path[402],q[5020];
int cost[402][402],flow[402][402];
bool t[402];

void Napkin_Makemap()
{
	NS=0;NT=2*n+1;
	for (i=1;i<=n;i++)
	{
		cost[NS][i]=0;flow[NS][i]=u[i];
		cost[i+n][NT]=0;flow[i+n][NT]=u[i];
		cost[NS][n+i]=p;flow[NS][n+i]=oo;
		if (i+1<=n)
		{
			cost[i][i+1]=0;flow[i][i+1]=oo;
		}
		if (i+t1<=n)
		{
			cost[i][i+t1+n]=c1;flow[i][i+t1+n]=oo;
		}
		if (i+t2<=n)
		{
			cost[i][i+t2+n]=c2;flow[i][i+t2+n]=oo;
		}
	}
}

void Napkin_SPFA()
{
	int i,head,tail;
	head=1;tail=1;q[head]=NS;t[NS]=true;f[NS]=0;
	do
	{
		for (i=1;i<=NT;i++)
			if (flow[q[head]][i]>0 && f[i]>f[q[head]]+cost[q[head]][i])
			{
				f[i]=f[q[head]]+cost[q[head]][i];path[i]=q[head];
				if (!t[i])
				{
					tail++;q[tail]=i;t[i]=true;
				}
			}
		t[q[head]]=false;head++;
	}while(head<=tail);
}

void Napkin_Findmin(int x)
{
	if (path[x]!=-1)
	{
		kk=min(kk,flow[path[x]][x]);
		Napkin_Findmin(path[x]);
	}
}

void Napkin_Addflow(int x)
{
	if (path[x]!=-1)
	{
		ans+=kk*cost[path[x]][x];
		flow[path[x]][x]-=kk;
		flow[x][path[x]]+=kk;
		cost[x][path[x]]=-cost[path[x]][x];
		Napkin_Addflow(path[x]);
	}
}

int main()
{
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d\n",&n);
	for (i=1;i<=n;i++) scanf("%d",&u[i]);
	scanf("%d %d %d %d %d\n",&p,&t1,&c1,&t2,&c2);
	Napkin_Makemap();	
	do
	{
		for(i=0;i<=NT;i++)
		{
			f[i]=oo;t[i]=false;path[i]=-1;
		}
		kk=oo;
		Napkin_SPFA();
		if (f[NT]==oo) break;
		Napkin_Findmin(NT);
		Napkin_Addflow(NT);
	}while(1==1);
	printf("%d\n",ans);
	return 0;
}