记录编号 24183 评测结果 AAAAAAAAAAAA
题目名称 [网络流24题] 餐巾 最终得分 100
用户昵称 Gravatarwo 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.