比赛 |
20100913 |
评测结果 |
WWWWWWWWWA |
题目名称 |
餐巾 |
最终得分 |
10 |
用户昵称 |
.Xmz |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-09-13 21:23:31 |
显示代码纯文本
#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;
for (edge *i=V[S];i;i=i->next)
{
if (i->t>NN) buy[i->t-NN]=inf - i->c;
}
for (int i=1;i<=NN;i++)
{
for (edge *j=V[i];j;j=j->next)
{
if (j->t>NN)
{
if (j->t==i+mm+NN) {sk[i]=inf-j->c;lk[j->t-NN]=inf-j->c;}
if (j->t==i+nn+NN) {sm[i]=inf-j->c;lm[j->t-NN]=inf-j->c;}
}
}
}
for (int i=1;i<=NN;i++)
{
printf("%d %d %d %d %d %d\n",need[i],buy[i],sk[i],sm[i],lk[i],lm[i]);
}
}