记录编号	23326	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2011-03-07 20:55:56	内存使用	0.86 MiB

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

using namespace std;

const int maxn=1000*2+1;
const int maxm=maxn*6*2+1;
const int inf=2000000000;
struct edge
{
	int t,c,v;
	edge *op,*next;
}*V[maxn],E[maxm];
int eh,S,T,ans;
int need[maxn],buy[maxn],sk[maxn],sm[maxn],lk[maxn],lm[maxn];
inline void addedge(int a,int b,int c,int v)
{
	E[++eh].next = V[a]; V[a]=E+eh; V[a]->t=b; V[a]->c=c; V[a]->v=v;
	E[++eh].next = V[b]; V[b]=E+eh; V[b]->t=a; V[b]->c=0; V[b]->v=-v;
	V[a]->op = V[b]; V[b]->op = V[a];
}
int NN,pp,mm,ff,nn,ss;

void makeflow()
{
	int t;
	cin>>NN;
	S=0;T=NN*2+1;
	for (int i=1;i<=NN;i++)
	{
		cin>>need[i];
	}
	cin>>pp>>mm>>ff>>nn>>ss;
	for (int i=1;i<=NN;i++)
	{
		t=need[i];
		addedge(0,i,t,0);
		addedge(0,i+NN,inf,pp);
		if (i+1<=NN) addedge(i,i+1,inf,0);
		if (i+mm<=NN) addedge(i,i+mm+NN,inf,ff);
		if (i+nn<=NN) addedge(i,i+NN+nn,inf,ss);
		addedge(i+NN,T,t,0);
	}
}

int ansflow,ansv;

bool inqueue[maxn*6];
int d[2*maxn];
edge *P[2*maxn];
int queue[6*maxn],qt,qw;
bool spfa()
{
	qt=0;qw=-1;
	queue[++qw]=S;
	inqueue[S]=true;
	memset(P,0,sizeof(P));
	for (int i=1;i<=T;i++) d[i]=inf;
	d[S]=0;
	while (qt<=qw)
	{
		int u=queue[qt];
		for (edge *e=V[u];e;e = e->next)
		{
			int v=e->t;
			if(e->c && d[v]>d[u]+e->v)
			{
				d[v]=d[u]+e->v;
				P[v]=e;
				if (!inqueue[v])
				{
					queue[++qw]=v;
					inqueue[v]=true;
				}
			}
		}
		inqueue[queue[qt++]]=false;
	}
	if (d[T]!=inf) return true;
	else return false;
}

void modifyflow()
{
	int nowp=T,minflow=inf,sumv=0;
	while (nowp!=S)
	{
		if (P[nowp]->c < minflow) minflow = P[nowp]->c;
		sumv+=P[nowp]->v;
		nowp = P[nowp]->op->t;
	}
	nowp=T;
	ansv+=minflow*sumv;
	ansflow+=minflow;
	while (nowp!=S)
	{
		P[nowp]->c -=minflow;
		P[nowp]->op->c +=minflow;
		nowp = P[nowp]->op->t;
	}
}

void spfaflow()
{
	while (spfa())
	{
		modifyflow();
	}
}


int main()
{
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	makeflow();
	spfaflow();
	cout<<ansv<<endl;
}