最大流SAP

houbin

type  node=record
v,n,f:longint;
end;
const maxn=410;
oo=1<<30;
var   e:array[0..maxn] of node;
vg,g,h:array[0..maxn] of longint;
flow,aug,find,s,t,a:longint;
n,m,cnt:longint;
procedure auge(u:longint);
var   mg,tg,p,v:longint;
begin
mg:=a-1;
tg:=aug;
if u=t then
begin
inc(flow,aug);
find:=1;
exit;
end;
p:=h;
while p>=0 do
begin
v:=e[p].v;
if e[p].f>0 then
begin
if g=g[v]+1 then
begin
if aug>e[p].f then aug:=e[p].f;
auge(v);
if g>=a then exit;
if find=1 then break;
aug:=tg;
end;
if mg>g[v] then mg:=g[v];
end;
p:=e[p].n;
end;
if find=0 then
begin
dec(vg[g]);
if vg[g]=0 then g:=n;
g:=mg+1;
inc(vg[g]);
end
else
begin
dec(e[p].f,aug);
inc(e[p xor 1].f,aug);
end;
end;
procedure add(u,v,c:longint);
begin
e[cnt].v:=v;
e[cnt].f:=c;
e[cnt].n:=h;
h:=cnt;
inc(cnt);
e[cnt].v:=u;
e[cnt].f:=0;
e[cnt].n:=h[v];
h[v]:=cnt;
inc(cnt);
end;
procedure init;
var   o,a,b,c:longint;
begin
fillchar(h,sizeof(h),255);
cnt:=0;
readln(m,n);
for o:=1 to m do
begin
readln(a,b,c);
add(a,b,c);
end;
end;
procedure maxflow;
begin
fillchar(vg,sizeof(vg),0);
fillchar(g,sizeof(g),0);
s:=1;
t:=n;
a:=n;
flow:=0;
while g<a do
begin
aug:=oo;
find:=0;
auge(s);
end;
writeln(flow);
end;
begin
assign(input,'a.in'); reset(input);
assign(output,'a.out'); rewrite(output);
init;
maxflow;
close(input);
close(output);
end.