实现功能:同前
程序还是一如既往的优美,虽然比起邻接矩阵的稍稍长了那么些,不过没关系这是必然,但更重要的一个必然是——速度将是一个质的飞跃^_^(这里面的point指针稍作了些创新——anti指针,这个指向当前弧的反向弧,便于路径增广时的操作,相比非递归里面非要用一个op函数来挨个找已经强多了!!!)
1 type 2 point=^node; 3 node=record 4 g,w:longint; 5 anti,next:point; 6 end; 7 var 8 i,j,k,l,m,n,ans,s,t:longint; 9 a:array[0..10000] of point;10 d,dv:array[0..10000] of longint;11 function min(x,y:longint):longint;inline;12 begin13 if xnil do28 begin29 if (p^.w>0) and (d[x]=(d[p^.g]+1)) then30 begin31 k:=dfs(p^.g,min(flow-dfs,p^.w));32 dec(p^.w,k);33 inc(p^.anti^.w,k);34 inc(dfs,k);35 if dfs=flow then exit;36 end;37 p:=p^.next;38 end;39 if d[s]=n then exit;40 dec(dv[d[x]]);41 if dv[d[x]]=0 then d[s]:=n;42 inc(d[x]);inc(dv[d[x]]);43 end;44 begin45 readln(n,m,s,t);46 for i:=1 to n do a[i]:=nil;47 for i:=1 to m do48 begin49 readln(j,k,l);50 add(j,k,l);51 end;52 fillchar(d,sizeof(d),0);53 fillchar(dv,sizeof(dv),0);54 dv[0]:=n;ans:=0;55 while d[s]