ZZXYY's blog

const
  maxe=1000000;
  maxn=40005;
type
  edge=record
         x,y,next,op:longint;
       end;
var
  e:array[0..maxe]of edge;
  a,gap,dis,pre,cur:array[0..maxn]of longint;
  n,m,i,j,k,s,t,u,v,cap,flow,mf:longint;
procedure adde(u,v,cap,cc:longint);
begin
  inc(k);
  e[k].y:=cap;
  e[k].x:=v;
  e[k].next:=a[u];
  e[k].op:=k+1;
  a[u]:=k;
  inc(k);
  e[k].y:=cc;
  e[k].x:=u;
  e[k].op:=k-1;
  e[k].next:=a[v];
  a[v]:=k;
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure sap;
var
  i,j,k,now,p,pp,dist:longint;
  f:boolean;
begin
  fillchar(dis,sizeof(dis),0);
  fillchar(gap,sizeof(gap),0);
  for i:=s to t do cur[i]:=a[i];
  mf:=0;
  now:=s;
  gap[t]:=t;
  flow:=2147483647;
  while dis[s]<=t do
  begin
    if now=t then
    begin
      flow:=2147483647;
      i:=s;
      while i<>t do
      begin
        flow:=min(flow,e[cur[i]].y);
        i:=e[cur[i]].x;
      end;
      i:=s;
      while i<>t do
      begin
        dec(e[cur[i]].y,flow);
        inc(e[e[cur[i]].op].y,flow);
        i:=e[cur[i]].x;
      end;
      mf:=mf+flow;
      now:=s;
    end;
    p:=cur[now];
    f:=true;
    while p<>0 do
    begin
      pp:=e[p].x;
      if (e[p].y>0) and (dis[now]=dis[pp]+1) then
      begin
        cur[now]:=p;
        pre[pp]:=now;
        now:=pp;
        f:=false;
        break;
      end;
      p:=e[p].next;
    end;
    if f then
    begin
      dec(gap[dis[now]]);
      if gap[dis[now]]=0 then break;
      cur[now]:=a[now];
      p:=a[now];
      dis[now]:=t+1;
      while p<>0 do
      begin
        pp:=e[p].x;
        if (e[p].y>0) then dis[now]:=min(dis[pp]+1,dis[now]);
        p:=e[p].next;
      end;
      inc(gap[dis[now]]);
      if now<>s then now:=pre[now];
    end;
  end;
end;
begin
  //assign(input,'1.in');
  //assign(output,'2.out');
  //reset(input);
  //rewrite(output);
  read(n,m);
  s:=0;
  t:=n+1;
  for i:=1 to n do
  begin
    read(u,v);
    adde(s,i,u,0);
    adde(i,t,v,0);
  end;
  for i:=1 to m do
  begin
    read(u,v,cap);
    adde(u,v,cap,cap);
  end;
  sap;
  writeln(mf);
  //close(input);
  //close(output);
end.</b>