ZZXYY's blog

const
  maxn=1005;
  maxe=50000;
var
  a,next,q,u,v,f,c:array[0..maxe]of longint;
  dis,pre,id:array[0..maxn]of longint;
  b:array[0..maxn]of boolean;
  i,j,n,m,p,qq,k,tot,s,t,mc:longint;
procedure adde(uu,vv,ff,cc:longint);
begin
  inc(tot);
  v[tot]:=vv;
  f[tot]:=ff;
  c[tot]:=cc;
  u[tot]:=tot+1;
  next[tot]:=a[uu];
  a[uu]:=tot;
  inc(tot);
  v[tot]:=uu;
  f[tot]:=0;
  c[tot]:=-cc;
  u[tot]:=tot-1;
  next[tot]:=a[vv];
  a[vv]:=tot;
end;
function spfa:boolean;
var
  head,tail,k,p,pp:longint;
begin
  fillchar(dis,sizeof(dis),$7f);
  fillchar(b,sizeof(b),true);
  head:=0;
  tail:=1;
  q[1]:=s;
  dis[s]:=0;
  b[s]:=false;
  repeat
    inc(head);
    if head>500000 then head:=1;
    k:=q[head];
    p:=a[k];
    b[k]:=true;
    while p<>t0 do
    begin
      pp:=v[p];
      if (f[p]>0) and (dis[k]+c[p]<dis [pp]) then
      begin
        dis[pp]:=dis[k]+c[p];
        pre[pp]:=k;
        id[pp]:=p;
        if b[pp] then
        begin
          inc(tail);
          if tail>500000 then tail:=1;
          b[pp]:=false;
          q[tail]:=pp;
        end;
      end;
      p:=next[p];
    end;
  until head>=tail;
  if dis[t]>1000000 then exit(false) else exit(true);
end;
procedure change;
var
  i,m:longint;
begin
  i:=t;
  m:=2147483647;
  while i<>s do
  begin
    if f[id[i]]<m then m:=f[id[i]];
    i:=pre[i];
  end;
  i:=t;
  while i<>s do
  begin
    dec(f[id[i]],m);
    inc(f[u[id[i]]],m);
    i:=pre[i];
  end;
  mc:=mc+m*dis[t];
end;
begin
  //assign(input,'1.in');
  //assign(output,'1.out');
  //reset(input);
  //rewrite(output);
  mc:=0;
  while spfa do change;
  writeln(mc);
  //close(input);
  //close(output);
end.</m></dis>