最大流模版题

注意输入的是m,n

program rq194;

type pnode=^tnode;

tnode=record

n,c:longint;

next,opp:pnode;

end;

const maxn=213;

maxint=longint($3f3f3f3f);

var g,arc,cur:array[1..maxn] of pnode;

d,estd,dlt,prev,dc:array[0..maxn] of longint;

n,m,ans,st,trm:longint;

function min(a,b:longint):longint; begin

if a<b then exit(a) else exit(b); end;

procedure ins(e1,e2,e3:longint);

var tmp:pnode;

begin

new(tmp);

with tmp^ do begin

n:=e2; c:=e3;

next:=g[e1];

opp:=nil;

end;

g[e1]:=tmp;

end;

procedure init;

var i,j,e1,e2,e3:longint;

begin

readln(m,n);

for i:=1 to m do begin

readln(e1,e2,e3);

ins(e1,e2,e3);

ins(e2,e1,0);

g[e1]^.opp:=g[e2];

g[e2]^.opp:=g[e1];

end;

fillchar(d,sizeof(d),0);

st:=1; trm:=n; cur:=g;

end;

procedure isap;

var i,j,k:longint;

begin

i:=st; dlt[st]:=maxint; prev[st]:=st; dc[0]:=n;

while d[st] < n do begin

while (cur[i]<>nil)and((not (d[i]=d[cur[i]^.n]+1))or(cur[i]^.c=0)) do begin

if cur[i]^.c>0 then estd[i]:=min(estd[i],d[cur[i]^.n]);

cur[i]:=cur[i]^.next;

end;

if cur[i]=nil then begin

dec(dc[d[i]]);

if dc[d[i]]=0 then break;

d[i]:=estd[i]+1;

inc(dc[d[i]]);

estd[i]:=n-1;

cur[i]:=g[i];

i:=prev[i];

end else begin

prev[cur[i]^.n]:=i;

dlt[cur[i]^.n]:=min(dlt[i],cur[i]^.c);

arc[cur[i]^.n]:=cur[i];

i:=cur[i]^.n;

if i=trm then begin

j:=dlt[trm];

inc(ans,j);

while i<>st do begin

dec(arc[i]^.c,j);

inc(arc[i]^.opp^.c,j);

i:=prev[i];

end;

end;

end;

end;

end;

begin

init;

isap;

writeln(ans);

end.