ac1249.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

{$Q-,R-}
program tju1249;
const
  maxn=1000;
  maxv=maxn*2+2;
  maxe=maxn*12;
var
  edge:array[1..maxe]of record pre,v1,v2:word;cap:byte;cost:integer;end;
  last,q,from:array[1..maxv]of word;
  dist:array[1..maxv]of longint;
  inq:array[1..maxv]of boolean;
  n,a,b,f,fa,fb,src,tar,e,i,x,r,ans:longint;
  fail:boolean;
procedure make_edge(a,b,c,d:longint);
  begin
    inc(e);with edge[e] do begin v1:=a;v2:=b;cap:=c;cost:=d;pre:=last[a];end;last[a]:=e;
    inc(e);with edge[e] do begin v1:=b;v2:=a;cap:=0;cost:=-d;pre:=last[b];end;last[b]:=e;
  end;
procedure aug;
  begin
    for i:=1 to n*2 do dist[i]:=maxlongint;dist[src]:=0;dist[tar]:=maxlongint;
    fillchar(inq,sizeof(inq),0);inq[src]:=true;
    f:=0;r:=1;q[1]:=src;
    repeat
      inc(f);if f>tar then f:=1;inq[q[f]]:=false;
      x:=last[q[f]];
      while x>0 do
        with edge[x] do begin
          if (cap>0) and (dist[v1]+cost<dist[v2]) then begin
            dist[v2]:=dist[v1]+cost;from[v2]:=x;
            if not inq[v2] then begin inc(r);if r>tar then r:=1;q[r]:=v2;inq[v2]:=true;end;
          end;
          x:=pre;
        end;
    until f=r;
    if dist[tar]=maxlongint then begin fail:=true;exit;end;

    f:=255;x:=tar;
    while x<>src do begin
      if edge[from[x]].cap<f then f:=edge[from[x]].cap;
      x:=edge[from[x]].v1;
    end;

    x:=tar;
    while x<>src do begin
      x:=from[x];
      inc(ans,edge[x].cost*f);
      dec(edge[x].cap,f);
      if odd(x) then inc(edge[x+1].cap,f) else inc(edge[x-1].cap,f);
      x:=edge[x].v1;
    end;
  end;
begin
  repeat
    fillchar(last,sizeof(last),0);
    read(n,a,b,f,fa,fb);src:=n*2+1;tar:=src+1;e:=0;
    for i:=1 to n do begin
      read(x);
      make_edge(src,i,x,0);
      make_edge(n+i,tar,x,0);
      make_edge(src,n+i,255,f);
    end;
    for i:=1 to n-a-1 do make_edge(i,n+i+a+1,255,fa);
    for i:=1 to n-b-1 do make_edge(i,n+i+b+1,255,fb);
    for i:=1 to n-1 do make_edge(i,i+1,255,0);

    ans:=0;fail:=false;
    repeat aug;until fail;
    writeln(ans);
  until seekeof;
end.