最天下午又听了一节课，勉强把MaxiumFlow的两个算法写出来了。其实两个算法的不同之处就在于寻找“增广链”的方式——Ford-Fulkerson是随便找一条，我就用了DFS；Edmonds-Karp要求找一条节点数最少的，我用BFS。但就是这样的差别，两个程序的执行效率不可同日而语——Edmonds-Karp可以过100，而Ford-Fulkerson过50时时间就不可忍受了（也许是我找增广链的方式不对，因为Fish大牛的Ford-Fulkerson明显效率比我高）。 另外，Fish大牛的两个程序都在100+行，而我的两个程序只在80+行（Edmonds-Karp甚至比Ford-Fulkerson少了5行），所以我怀疑我是不是少写点东西，但就目前，我用随机数据测试，跟Fish大牛的Edmonds-Karp结果是一样的。我没有看懂Fish大牛的程序，直接按照MIT课上讲的东西写的。
program ford_fulkerson; var g,gf:array[1..100,1..100] of longint; path:array[0..100] of longint; inpath:Array[1..100] of boolean; n,f,s,t:longint; find:boolean; procedure findpath(s,z:longint); var i:longint; begin for i:=1 to n do begin if (gf[s,i]>0) and (not inpath[i]) then begin path[z]:=i; inpath[i]:=true; if i=t then begin path[0]:=z; find:=true; inpath[i]:=false; break; end; findpath(i,z+1); inpath[i]:=false; end; if find then break; end; end; procedure countf; var i:longint; begin f:=maxint; for i:=1 to path[0]-1 do if f>gf[path[i],path[i+1]] then f:=gf[path[i],path[i+1]]; end; procedure maxflow; var i:longint; begin findpath(s,2); repeat countf; for i:=1 to path[0]-1 do begin dec(gf[path[i],path[i+1]],f); inc(gf[path[i+1],path[i]],f); end; find:=false; findpath(s,2); until not find; end; procedure buildg; var i,j:longint; begin for i:=1 to n do for j:=1 to n do begin dec(g[i,j],gf[i,j]); if g[i,j]<0 then g[i,j]:=0; end; j:=0; for i:=1 to n do inc(j,g[i,t]); writeln(s,'-->',t,': ',j); end; procedure init; var i,j:longint; begin readln(n,s,t); while not eof do begin readln(i,j,g[i,j]); gf[i,j]:=g[i,j]; end; path[1]:=s; inpath[1]:=true; end; begin init; maxflow; buildg; end. program edmonds_karp; var g,gf:array[1..100,1..100] of longint; q,path,f:array[1..100] of longint; inpath:array[1..100] of boolean; n,s,t,z:longint; procedure find; var i,j:longint; begin z:=1; i:=0; while (i<z) and (not inpath[t]) do begin inc(i); for j:=1 to n do if (gf[q[i],j]>0) and (not inpath[j]) then begin inc(z); q[z]:=j; inpath[j]:=true; path[j]:=q[i]; f[j]:=f[q[i]]; if f[j]>gf[q[i],j] then f[j]:=gf[q[i],j]; end; end; while (q[z]<>t) and (z>1) do dec(z); fillchar(inpath,sizeof(inpath),false); inpath[s]:=true; end; procedure maxflow; var i:longint; begin find; repeat i:=q[z]; while i<>s do begin dec(gf[path[i],i],f[q[z]]); inc(gf[i,path[i]],f[q[z]]); i:=path[i]; end; find; until z=1; end; procedure buildg; var i,j:longint; begin for i:=1 to n do for j:=1 to n do begin dec(g[i,j],gf[i,j]); if g[i,j]<0 then g[i,j]:=0; end; j:=0; for i:=1 to n do inc(j,g[i,t]); writeln(s,'-->',t,': ',j); end; procedure init; var i,j:longint; begin readln(n,s,t); while not eof do begin readln(i,j,g[i,j]); gf[i,j]:=g[i,j]; end; f[1]:=maxint; q[1]:=s; path[1]:=s; inpath[1]:=true; end; begin init; maxflow; buildg; end.
