实现功能:首行输入N,M,S,T,代表这张图N个点,M条边,源点为S,汇点为T;接下来T行输入个边的出发点、终点和权值;输出最大流
原理:sap网络流算法(详见百度百科,个人觉得这个模板已经不错了,虽然本人暂时还未考虑引入邻接表进行优化)(推荐模板题:Codevs1993)
1 var
2 i,j,k,l,m,n,ans,aug,s,t,tmp,jl,mi:longint;
3 flag:boolean;
4 vh,dis,di,his,pre:array[0..10000] of longint;
5 map:array[0..2050,0..2050] of longint;
6 function min(x,y:longint):longint;inline;
7 begin
8 if x<y then min:=x else min:=y;
9 end;
10 begin
11 readln(n,m,s,t);
12 fillchar(map,sizeof(map),0);
13 for i:=1 to m do
14 begin
15 readln(j,k,l);
16 map[j,k]:=map[j,k]+l;
17 end;
18 i:=s;ans:=0;aug:=maxlongint;
19 fillchar(dis,sizeof(dis),0);
20 for i:=1 to n do di[i]:=1;
21 i:=s;
22 while dis[s]<n do
23 begin
24 flag:=false;
25 his[i]:=aug;
26 for j:=di[i] to n do
27 begin
28 if (map[i,j]>0) and (dis[i]=(dis[j]+1)) then
29 begin
30 aug:=min(aug,map[i,j]);
31 pre[j]:=i;di[i]:=j;
32 i:=j;flag:=true;
33 if i=t then
34 begin
35 ans:=ans+aug;
36 while i<>s do
37 begin
38 tmp:=i;
39 i:=pre[i];
40 map[i,tmp]:=map[i,tmp]-aug;
41 map[tmp,i]:=map[tmp,i]+aug;
42 end;
43 aug:=maxlongint;
44 end;
45 break;
46 end;
47 end;
48 if flag then continue;
49 jl:=-1;mi:=n-1;
50 for j:=1 to n do
51 begin
52 if (map[i,j]>0) and (dis[j]<mi) then
53 begin
54 mi:=dis[j];
55 jl:=j;
56 end;
57 end;
58 di[i]:=jl;
59 dec(vh[dis[i]]);
60 if vh[dis[i]]=0 then break;
61 dis[i]:=mi+1;
62 inc(vh[dis[i]]);
63 if i<>s then
64 begin
65 i:=pre[i];
66 aug:=his[i];
67 end;
68 end;
69 writeln(ans);
70 end.
71