记录编号 |
24183 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
[网络流24题] 餐巾 |
最终得分 |
100 |
用户昵称 |
wo shi 刘畅 |
是否通过 |
通过 |
代码语言 |
Pascal |
运行时间 |
1.473 s |
提交时间 |
2011-03-29 16:12:11 |
内存使用 |
5.85 MiB |
显示代码纯文本
const
oo=99999999;
var
n,min,ans:longint;
c,w:array[0..500,0..500]of longint;
q:array[0..1000000]of longint;
b:array[0..500]of boolean;
f,last:array[0..500]of longint;
procedure bian(x,y,cc,ww:longint);
begin
c[x,y]:=cc;
w[x,y]:=ww;
w[y,x]:=-ww;
end;
procedure init;
var
i,k1,k2,m1,m2,p:longint;
r:array[0..10000]of longint;
begin
assign(input,'napkin.in'); reset(input);
assign(output,'napkin.out'); rewrite(output);
readln(n);
for i:=2 to n+1 do read(r[i]);
readln(p,k1,k2,m1,m2);
for i:=2 to n+1 do
begin
bian(1,i,r[i],0);
bian(1,i+n,oo,p);
bian(i+n,n+n+2,r[i],0);
if i<=n then bian(i,i+1,oo,0);
if i+k1<=n+1 then bian(i,i+k1+n,oo,k2);
if i+m1<=n+1 then bian(i,i+m1+n,oo,m2);
end;
n:=n+n+2;
end;
procedure goformin;
var
i,j:longint;
begin
i:=n;
while last[i]<>0 do
begin
j:=i;
i:=last[j];
if c[i,j]<min then min:=c[i,j];
end;
end;
procedure change;
var
i,j:longint;
begin
i:=n;
while last[i]<>0 do
begin
j:=i;
i:=last[j];
dec(c[i,j],min);
inc(c[j,i],min);
end;
inc(ans,min*f[n]);
end;
procedure spfa;
var
h,t,x,i:longint;
begin
for i:=1 to n do
begin
q[i]:=0;
b[i]:=false;
f[i]:=oo;
last[i]:=0;
end;
h:=1;
t:=1;
f[1]:=0;
q[1]:=1;
b[1]:=true;
repeat
x:=q[h];
for i:=1 to n do
if (c[x,i]>0)and(f[x]+w[x,i]<f[i]) then
begin
f[i]:=f[x]+w[x,i];
if not b[i] then
begin
b[i]:=true;
inc(t);
q[t]:=i;
end;
last[i]:=x;
end;
b[x]:=false;
inc(h);
until h>t;
if f[n]<>oo then
begin
min:=oo;
goformin;
change;
end;
end;
begin
init;
repeat
spfa;
until f[n]=oo;
writeln(ans);
close(input);
close(output);
end.