P1221: [HNOI2001] 软件开发

  1 const inf=1000000000; maxe=1000000; maxn=10000;
  2 type
  3   node=record
  4     f,t,c,d:longint;
  5   end;
  6 var n,a,b,fbuy,fa,fb,i,s,t,x,num,ans,temp:longint;
  7 e:array[0..maxe] of node;
  8 head,go,d:array[0..maxn] of longint;
  9 f:array[0..maxe] of longint;
 10 p:array[0..maxn] of boolean;
 11 procedure insert(u,v,x,y:longint);
 12 begin
 13   e[num].f:=head[u];
 14   e[num].t:=v;
 15   e[num].c:=x;
 16   e[num].d:=y;
 17   head[u]:=num;
 18   inc(num);
 19 end;
 20 procedure add(u,v,x,y:longint);
 21 begin
 22   insert(u,v,x,y);
 23   insert(v,u,0,-y);
 24 end;
 25 function spfa:boolean;
 26 var l,r,edge,now,v:longint;
 27 begin
 28   fillchar(p,sizeof(p),true);
 29   fillchar(go,sizeof(go),255);
 30   for l:=1 to t do d[l]:=inf;
 31   l:=1; r:=1; f[1]:=s; d[s]:=0; p[s]:=false; temp:=0;
 32   while l<=r do
 33     begin
 34       now:=f[l];
 35       edge:=head[now];
 36       while edge<>-1 do
 37         begin
 38           v:=e[edge].t;
 39           if (d[v]>d[now]+e[edge].d) and (e[edge].c>0) then
 40             begin
 41               d[v]:=d[now]+e[edge].d;
 42               go[v]:=edge;
 43               if p[v] then
 44                 begin
 45                   p[v]:=false;
 46                   inc(r);
 47                   f[r]:=v;
 48                 end;
 49             end;
 50           edge:=e[edge].f;
 51         end;
 52       inc(l);
 53       p[now]:=true;
 54     end;
 55   if d[t]=inf then exit(false)
 56     else begin
 57       temp:=d[t];
 58       exit(true);
 59     end;
 60 end;
 61 function min(a,b:longint):longint;
 62 begin if a>b then exit(b) else exit(a); end;
 63 function calc:longint;
 64 var now:longint;
 65 begin
 66   now:=t; calc:=inf;
 67   while go[now]<>-1 do
 68     begin
 69       calc:=min(calc,e[go[now]].c);
 70       now:=e[go[now] xor 1].t;
 71     end;
 72   now:=t;
 73   while go[now]<>-1 do
 74     begin
 75       dec(e[go[now]].c,calc);
 76       inc(e[go[now] xor 1].c,calc);
 77       now:=e[go[now] xor 1].t;
 78     end;
 79 end;
 80 begin
 81   readln(n,a,b,fbuy,fa,fb);
 82   fillchar(e,sizeof(e),255);
 83   fillchar(head,sizeof(head),255);
 84   s:=2*n+1; t:=s+1;
 85   for i:=1 to n do
 86     begin
 87       read(x);
 88       if i+1<=n then add(i,i+1,inf,0);
 89       if i+a+1<=n then add(i,n+i+a+1,inf,fa);
 90       if i+b+1<=n then add(i,n+i+b+1,inf,fb);
 91       add(s,n+i,inf,fbuy);
 92       add(s,i,x,0);
 93       add(n+i,t,x,0);
 94     end;
 95   while spfa do
 96     begin
 97       //writeln(temp);
 98       inc(ans,temp*calc);
 99     end;
100   writeln(ans);
101 end.