引言

　　過去聽起來高深莫測的網絡流算法，現在已飛入尋常百姓家了，對于每一個OIER，網絡流是一個神圣的東西（個人見解），但神圣的同時，它并不是那樣抽象，最形象的模型就是水流，從長江源點無限的向外流水，而大海（匯點）則在不斷地‘喝水’，當然，你也可以不把它想成水，或者是其他一切可以流動的東西。而事實上，有些東西的流動比較流暢，而某些東西可能相對而言比較粘稠，流速更慢，因此，就產生了一個問題，單位時間內的總流量最多多少，這里會根據流速給定單位時間內的流量，這就是最先開啟網絡流之門的最大流算法，它的解決方式將在后面談到，再想一下，如果水管是另一個物流公司所有，那么你會根據從哪里運到哪里付出一定的代價，?為了你自己的利潤，顯然要找一個在運的東西最多的前提下有最小費用的方案，這就引出了下一個問題，最小費用最大流。再引用某牛一句話“當然也有有錢沒處花的傻子，去求最大費用最大流”，而事實上，題目會出現這個模型，為了避免你成為傻瓜，現在你要給它一個新的定義：最大收益流，這時的你，變成了物流公司的經理，而客戶的路線由你規劃，為了你的錢包，最大收益必不可少。

?

正文

　第一部分.概念性問題(基本定理及定義)

?? ? ? ?對于一些網絡流新手來說，有必要知道一些基本定義和基本定理，這些雖然看起來理論價值不大，但是現在的許多網絡流描述需要這些專業性的詞語，所以還是　　有些了解為好。

?? ? ??首先對于圖G

?? ????G?的流是一個實值函數?f，?f?(u,?v)?表示頂點?u?到頂點?v?的流，它可以為正， 為零，也可以為負，且滿足下列三個性質：

1.容量限制：對所有u,?v??V?，要求?f?(u,?v)?￡?c(u,?v)?。?反對稱性：對所有u,?v??V?，要求?f?(u,?v)?=-?f?(v,?u)?。

2.流守恒性：對所有u??V?-{s,?t}?，要求???f?(u,?v)?=?0?。

3.整個流網絡?G?的流量?f?=???f?(s,?v)?或?f=???f?(u,?t)?。

接下來定義各種算法中都要用到的一些東東：

1.殘留網絡

給定一個流網絡G?=?(V?,?E)?和流?f，由?f?壓得的?G?的殘留網絡Gf=?(V?,?E?f?)?，定義?c?f?(u,?v)?為殘留網絡G?f??中邊?(u,?v)?的容量。如果弧?(u,?v)???E?或弧?(v,?u)???E?，則?弧?(u,?v)???E?f?，且?c?f?(u,?v)?=?c(u,?v)?-?f?(u,?v)?。

??殘留網絡又被稱為剩余圖。

2.點的高度和層次，這是兩個相對的概念，高度的定義為到匯點的最短路徑長度，而層次則是指到源點的最短路徑長度（這里的路徑長度按照各個邊的長度都為1算），這兩個量是在最大流算法中貫穿始末的利器。

接下來引入最大流最小割定理

?對了，可能有同學還不知道什么是最小割，在這里提一下

?流網絡?G?=?(V?,?E)?的割?(S?,T?)?將V?劃分成?S?和T?=?V?-?S?兩部分，使得?s???S?，t??T?。定義割?(S?,T?)?的容量為?c(S?,T?),

??對?于?最?小?的?c?，?它?是?最?小?割?。

3. ?最?大?流?最?小?割?定?理

?　　?在?流?網??絡?中，最?小?割?的?容?量?等?于?最?大?流?的?流?量?。（證?明?再?次?略?過?）

?

???第二部分.最大流的算法

下面步入與實際問題更加接近的算法實現部分，首先給出問題，給定一個流網絡，求源到匯在單位時間內的最大流量。

最簡單而效率較好的算法 是基于增廣路的算法，這類算法在王欣上大牛的論文中有詳細介紹，但我仍然想談談我的想法，希望能起到拋磚引玉的作用。基于增廣路的算法主要有兩種:MPLA,Dinic,SAP.其中最簡單的是MPLA,最實用最簡潔也是最多人用的是Dinia,SAP的范圍也很廣，加上GAP優化后的效率也讓人咋舌，這也是最近SAP大泛濫的原因吧！個人比較喜歡Dinic，數據變態就用最高標號預流推進，SAP用的比較少，當然，用什么算法還是看你自己的感覺吧。有些人認為增廣路算法格式低效，于是想出了對于每個節點操作的算法，這類算法以預留推進為頂梁柱，MPM也勉強歸入這一類吧。

?

1.MPLA算法

即最短路徑增值算法，可以有一個簡單的思想，每次都找一條從源到匯的路徑來增廣，直到不能增廣為止，之中算法的正確性是可以保證的，但效率不盡如人意，有些時候，把事情格式化反而有益，這里的MPLA就是這樣，它只在層次圖中找增廣路，構建出層次圖之后，用BFS不斷增廣，直到當前層次圖中不再有增廣路，再重新構建層次圖，如果匯點不在層次圖內，則源匯不再連通，最大流已經求出，否則繼續執行增廣，如此反復，就可以求出最大流，在程序實現時層次圖不用被構建出來，只需要BFS出各點的距離標號，找路徑時判斷對于f(u,v)是否有d[u]+1=d[v]即可。

如果每建一次層次圖成為一個階段，則在最短路徑增值算法中，最多有N個階段，證明再次略過。

因此在整個算法中，最多有N個階段，每個階段構建層次圖的BFS時間復雜度為O(m),建N次，因此構建層次圖的總時間為O(mn),而在增廣過程中，每一次增廣至少刪除一條邊，因此增廣m次，加上修改流量的時間，每一階段的增廣時間為O(m*(m+n)),共有N個階段，所以復雜度為O(n*m*(m+n))=O(nm^2),這也是該算法的時間復雜度。

?

2.Dinic算法

MPLA雖然簡單，但經常會點超時，我們把增廣過程中的BFS改成DFS，效率會有比較大的提高么？答案是肯定的，至此我們已經得到了Dinic的算法流程，只是將MPLA的增廣改為DFS，就能寫出那美妙的Dinic了，同樣，分析一下時間，在DFS過程中，會有前進和后退兩種情況，最多前進后退N次，而增廣路最多找M次，再加上N個階段，所以Dinic的復雜度就是O(mn^2)，事實上，它也確實比MPLA快很多，簡潔而比較高效，這也是許多OIER選擇Dinic的理由了吧，畢竟，寫它可能會節省出較長時間來完成其他題目.

1 2 program dinic(input,output); 3 var 4 f : array[0..1000,0..1000] of longint; 5 number : array[0..1000] of longint; 6 q : array[0..10000] of longint; 7 n,m,ans,s,t : longint; 8 procedure init; 9 var 10 x,y,c : longint; 11 i : longint; 12 begin 13 readln(m,n); 14 s:=1; 15 t:=n; 16 fillchar(f,sizeof(f),0); 17 for i:=1 to m do 18 begin 19 readln(x,y,c); 20 inc(f[x,y],c); 21 end; 22 end; { init } 23 function min(aa,bb :longint ):longint; 24 begin 25 if aa<bb then 26 exit(aa); 27 exit(bb); 28 end; { min } 29 function bfs(): boolean; 30 var 31 head,tail : longint; 32 now,i : longint; 33 begin 34 fillchar(number,sizeof(number),0); 35 head:=0; 36 tail:=1; 37 q[1]:=s; 38 number[s]:=1; 39 while head<tail do 40 begin 41 inc(head); 42 now:=q[head]; 43 for i:=1 to n do 44 if f[now,i]>0 then 45 if number[i]=0 then 46 begin 47 number[i]:=number[now]+1; 48 inc(tail); 49 q[tail]:=i; 50 end; 51 end; 52 if number[t]=0 then 53 exit(false); 54 exit(true); 55 end; { bfs } 56 function dfs(now,flow :longint ):longint; 57 var 58 tmp,i : longint; 59 begin 60 if now=t then 61 exit(flow); 62 for i:=1 to n do 63 if number[i]=number[now]+1 then 64 if f[now,i]>0 then 65 begin 66 tmp:=dfs(i,min(flow,f[now,i])); 67 if tmp<>0 then 68 begin 69 inc(f[i,now],tmp); 70 dec(f[now,i],tmp); 71 exit(tmp); 72 end; 73 end; 74 exit(0); 75 end; { dfs } 76 procedure main; 77 var 78 tmp : longint; 79 begin 80 ans:=0; 81 while bfs() do 82 begin 83 tmp:=dfs(s,maxlongint>>2); 84 while tmp<>0 do 85 begin 86 inc(ans,tmp); 87 tmp:=dfs(s,maxlongint>>2); 88 end; 89 end; 90 writeln(ans); 91 end; { main } 92 begin 93 init; 94 main; 95 end.

?

3.SAP算法

??? SAP也是找最短路徑來增廣的算法，有這樣一句話：SAP算法更易理解，實現更簡單，效率更高，而也有測試表明，SAP加上重要的GAP優化后，效率僅次于最高標號預流推進算法，因此如果你想背一個模板，SAP是最佳選擇。SAP在增光時充分的利用了以前的信息，當按照高度找不到增廣路時，它會對節點重新標號，h[i]=min{h[j]}+1(c[i,j]>0)，這也是SAP比較核心的思想，而根據這個我們可以發現，當高度出現間隙時，一定不會存在增廣路了，算法已經可以結束，因此，這里引入間隙優化(GAP),即出現間隙時結束算法。

????在算法實現中，初始標號可以全部置為0，在增廣過程中在逐漸提升高度，時間上可能會有常數的增加，但不改變漸進時間復雜度。同時為了簡潔，SAP實現時用遞歸，代碼不過80行左右。

1 View Code 2 program sap(input,output); 3 var 4 c : array[0..1000,0..1000] of longint; 5 h,vh : array[0..1000] of longint; 6 flow,n,m,ans : longint; 7 tmpflow : longint; 8 can : boolean; 9 procedure init; 10 var 11 i,j : longint; 12 xx,yy,cc : longint; 13 begin 14 fillchar(c,sizeof(c),0); 15 fillchar(h,sizeof(h),0); 16 ans:=0; 17 readln(m,n); 18 for i:=1 to m do 19 begin 20 readln(xx,yy,cc); 21 inc(c[xx,yy],cc); 22 end; 23 end; { init } 24 procedure dfs(now : longint ); 25 var 26 min,tmp : longint; 27 i : longint; 28 begin 29 min:=n-1; 30 tmp:=tmpflow; 31 if now=n then 32 begin 33 can:=true; 34 inc(ans,tmpflow); 35 exit; 36 end; 37 for i:=1 to n do 38 if c[now,i]>0 then 39 begin 40 if h[i]+1=h[now] then 41 begin 42 if c[now,i]<tmpflow then 43 tmpflow:=c[now,i]; 44 dfs(i); 45 if h[1]>=n then 46 exit; 47 if can then 48 break; 49 tmpflow:=tmp; 50 end; 51 if h[i]<min then 52 min:=h[i]; 53 end; 54 if not can then 55 begin 56 dec(vh[h[now]]); 57 if vh[h[now]]=0 then 58 h[1]:=n; 59 h[now]:=min+1; 60 inc(vh[h[now]]); 61 end 62 else 63 begin 64 dec(c[now,i],tmpflow); 65 inc(c[i,now],tmpflow); 66 end; 67 end; { dfs } 68 begin 69 init; 70 fillchar(vh,sizeof(vh),0); 71 vh[0]:=n; 72 while h[1]<n do 73 begin 74 tmpflow:=maxlongint>>2;; 75 can:=false; 76 dfs(1); 77 end; 78 writeln(ans); 79 end.

?

4.MPM算法

????這個算法我還沒有實踐過，因為它的實現過程比較繁瑣，而且時間效率不高，是一個只具有理論價值的算法，這個算法每次都處理單獨節點，記每個節點入流和與出流和的最小值作為thoughput(now)（定義在非源匯點），每次先從now向匯推大小為thoughput(now)的流量，在從點now向源點拉大小為thoughput(now)的流量，刪除該節點，繼續執行直到圖中只剩下源匯。時間復雜度為O(n^3)，但時間常數較大，時間效率不高。

?

5.預留推進算法

????以上的算法中，基本上都需要從大體上來把握全局，而預留推進算法則是將每一個頂點看作了一個戰場，分別對他們進行處理，在處理過程中，存在某些時間不滿足流量收支平衡，所以對預先推出的流叫做預流，下面來看算法如何將預流變成最大流的。

????預留推進算法有兩個主過程，push和relabel，即推進和重標號，它是在模擬水流的過程，一開始先讓源的出弧全部飽和，之后隨著時間的推移，不斷改變頂點的高度，而又規定水流僅能從高處流向低處，所以在模擬過程中，最終會有水流入匯，而之前推出的多余的水則流回了源，那么我們每次處理的是什么節點呢？把當前節點內存有水的節點稱為活躍節點，每次對活躍節點執行推流操作，直到該節點不再活躍，如果不能再推流而當前節點仍未活躍節點，就需要對它進行重新標號了，標號后再繼續推流，如此重復，直到網絡中不再存在活躍節點為止，這時源的流出量就是該網絡的最大流。注意，對于活躍節點的定義，不包括源匯，否則你會死的很慘。

????樸素的預留推進的效率還過得去，最多進行nm次飽和推進和n^2m次不飽和推進，因此總的時間復雜度為O(mn^2)

????事實上，如同增廣路算法引入層次圖一樣，定下一些規則，可以讓預留推進算法有更好的時間效率，下面介紹相對而言比較好實現的FIFO預留推進算法，它用一個隊列來保存活躍節點，每次從隊首取出一個節點進行推進，對一個節點relabel之后把它加到隊尾，如此執行，直到隊列為空，這樣一來，預留推進算法的時間復雜度降為O(n^3),實現的時候，可以加上同樣的間隙優化，但注意，出現間隙時不要馬上退出，將新標號的的高度置為n+1，繼續執行程序，這樣會讓所有的剩水流回源，滿足流量收支平衡，以便最后的統計工作。

1 View Code 2 program preflow(input,output); 3 var 4 f,c : array[0..2000,0..2000] of longint; 5 q,h,vh,e : array[0..2000] of longint; 6 m,n,s,t : longint; 7 flow : longint; 8 procedure init; 9 var 10 i,j : longint; 11 xx,yy,cc : longint; 12 begin 13 readln(m,n); 14 fillchar(f,sizeof(f),0); 15 fillchar(c,sizeof(c),0); 16 fillchar(e,sizeof(e),0); 17 for i:=1 to m do 18 begin 19 readln(xx,yy,cc); 20 inc(c[xx,yy],cc); 21 end; 22 s:=1; 23 t:=n; 24 end; { init } 25 procedure main; 26 var 27 i,j : longint; 28 head,tail : longint; 29 now,tmp,tmph : longint; 30 begin 31 flow:=0; 32 h[s]:=n; 33 head:=0; 34 tail:=0; 35 for i:=1 to n do 36 begin 37 e[i]:=c[s,i]; 38 f[s,i]:=c[s,i]; 39 f[i,s]:=-f[s,i]; 40 if (e[i]>0)and(i<>t) then 41 begin 42 inc(tail); 43 q[tail]:=i; 44 inc(vh[h[i]]); 45 end; 46 end; 47 while head<tail do 48 begin 49 inc(head); 50 now:=q[head]; 51 for i:=1 to n do 52 if (c[now,i]>f[now,i])and(h[now]=h[i]+1)and(e[now]>0) then 53 begin 54 tmp:=c[now,i]-f[now,i]; 55 if tmp>e[now] then 56 tmp:=e[now]; 57 inc(f[now,i],tmp); 58 dec(f[i,now],tmp); 59 dec(e[now],tmp); 60 inc(e[i],tmp); 61 if (e[i]=tmp)and(i<>s)and(i<>t) then 62 begin 63 inc(tail); 64 q[tail]:=i; 65 end; 66 end; 67 if (e[now]>0)and(now<>s)and(now<>t) then 68 begin 69 tmph:=h[now]; 70 dec(vh[tmph]); 71 h[now]:=$FFFF; 72 for i:=1 to n do 73 if (c[now,i]>f[now,i])and(h[now]>h[i]+1) then 74 h[now]:=h[i]+1; 75 inc(tail); 76 q[tail]:=now; 77 inc(vh[h[now]]); 78 if vh[tmph]=0 then 79 for i:=1 to n do 80 if (h[i]>tmph)and(h[i]<n) then 81 begin 82 dec(vh[h[i]]); 83 h[i]:=n; 84 inc(vh[n]); 85 end; 86 end; 87 end; 88 flow:=0; 89 for i:=1 to n do 90 inc(flow,f[s,i]); 91 end; { main } 92 begin 93 init; 94 main; 95 writeln(flow); 96 end.

?

????下面介紹最后一個，也是編程難度最大，時間表現不同凡響的算法，最高標號預流推進，它的思想是既然水是從高處向低處流的，那么如果從低處開始會做許多重復工作，不如從最高點開始流，留一次就解決問題。再直觀一些，引用黑書上的話“讓少數的節點聚集大量的盈余，然后通過對這些節點的檢查把非飽和推進變成一串連續的飽和推進”。在程序現實現時，用一個表list來儲存所有的活躍節點，其中list(h)存儲高的為h的活躍節點，同時記錄一個level,為最高標號，每次查找時依次從level,level-1……查找，直到找到節點為止，這時從表內刪掉這個節點，對它進行Push,Relabel操作，直到該節點不再活躍，繼續進行，直到表內不在存在活躍節點。

?????它的復雜度為O(n^2*m^(1/2)),時間效率很優秀（當然，如果你刻意構造卡預留推進的數據，它比MPLA還慢也是有可能的）。

1 View Code 2 program hign_node_flow(input,output); 3 var 4 c : array[0..1000,0..1000] of longint; {保存原圖} 5 f : array[0..1000,0..1000] of longint; {保存當前的預流圖} 6 h : array[0..1000] of longint; {保存各個節點當前高度} 7 vh : array[0..1000] of longint; {保存各個高度節點的數量} 8 e : array[0..1100] of longint; {保存各個節點的盈余} 9 level : longint; {當前所有活躍節點的最高高度} 10 l : array[0..1000,0..1000] of longint; {保存活躍節點的表,l[i,0]表示高度為i的活躍節點數，這也是不能用vh數組的原因} 11 n,m,s,t : longint; {節點數，邊數，源，匯} 12 listsum : longint; {記錄當前在表內的元素個數} 13 flow : longint; {記錄流量} 14 inlist : array[0..1000] of boolean; {節點是否在表內} 15 q : array[0..10000] of longint; {用于BFS擴展的隊列} 16 procedure init; 17 var 18 i,xx,yy,cc : longint; 19 begin 20 readln(m,n); 21 fillchar(f,sizeof(f),0); 22 fillchar(c,sizeof(c),0); 23 fillchar(e,sizeof(e),0); 24 fillchar(h,sizeof(h),0); 25 fillchar(vh,sizeof(vh),0); 26 for i:=1 to m do 27 begin 28 readln(xx,yy,cc); 29 inc(c[xx,yy],cc);{注意某些情況下有重邊，這樣處理比較保險} 30 end; 31 s:=1; 32 t:=n; 33 end; { init } 34 procedure insect(now :longint ); {在活躍節點表內插入節點now} 35 begin 36 inlist[now]:=true; {標記now節點在表內} 37 inc(listsum); {表中元素增加1} 38 inc(l[h[now],0]); {高度為h[now]的活躍節點數增加1} 39 l[h[now],l[h[now],0]]:=now; {表中高度為h[now]的第l[h[now],0]個活躍節點為now} 40 if h[now]>level then {更新活躍節點最高高度} 41 level:=h[now]; 42 end; { insect } 43 procedure bfs(); {利用BFS(反向的)，求的各個節點的高度} 44 var 45 head,tail,i : longint; 46 begin 47 head:=0; 48 tail:=1; 49 q[1]:=t; 50 h[t]:=1; {匯點的高度為1} 51 while head<tail do 52 begin 53 inc(head); 54 for i:=1 to n do 55 if c[i,q[head]]>0 then {存在邊} 56 if h[i]=0 then {i節點高度沒有求出} 57 begin 58 h[i]:=h[q[head]]+1; {求的節點i的高度} 59 inc(tail); 60 q[tail]:=i; 61 end; 62 end; 63 end; { bfs } 64 procedure previous(); {預流推進的預處理} 65 var 66 i : longint; 67 begin 68 for i:=1 to n do 69 begin 70 e[i]:=c[s,i]; {讓源點的出弧飽和，則弧的指向點的盈余要改變} 71 f[s,i]:=c[s,i]; {源點出弧飽和} 72 f[i,s]:=-f[s,i]; {反向弧的處理} 73 if (e[i]>0)and(i<>t)and(not inlist[i]) then {節點i成為活躍節點,且不是匯點，沒有在表內(其實也不可能在表內)} 74 insect(i); 75 end; 76 h[1]:=n; 77 for i:=1 to n-1 do 78 inc(vh[h[i]]); 79 end; { previous } 80 function find(level :longint ):longint; {傳入當前活躍節點集合的最高高度} 81 var 82 i : longint; 83 begin 84 for i:=level downto 1 do {枚舉節點集合} 85 if l[i,0]<>0 then {存在節點} 86 begin 87 find:=l[i,l[i,0]]; {返回表的尾元素} 88 inlist[l[i,l[i,0]]]:=false; {返回節點不再表內} 89 dec(l[i,0]); 90 dec(listsum); {表中元素個數減一} 91 while (l[level,0]=0)and(level>0) do {更新level的值} 92 dec(level); 93 exit; 94 end; 95 exit(0); {沒有找到節點就返回0} 96 end; { find } 97 procedure push(now :longint ); {推流操作} 98 var 99 i : longint; 100 tmp : longint; 101 begin 102 for i:=1 to n do 103 if (c[now,i]>f[now,i])and(h[now]=h[i]+1)and(e[now]>0) then {如果當前節點有盈余且有出弧不飽和} 104 begin 105 tmp:=c[now,i]-f[now,i]; {tmp記錄對弧而言能增廣的量} 106 if tmp>e[now] then {這里能增廣的量=min(tmp,盈余)} 107 tmp:=e[now]; 108 inc(f[now,i],tmp); {增廣操作} 109 dec(f[i,now],tmp); 110 inc(e[i],tmp); {修改節點盈余} 111 dec(e[now],tmp); 112 if (not inlist[i])and(e[i]=tmp)and(i<>t) then {接受流的節點一定成為活躍節點且不再表內，又不是匯點} 113 insect(i); 114 end; 115 end; { push } 116 procedure relable(now : longint ); {重新標號} 117 var 118 i : longint; 119 tmph : longint; 120 begin 121 tmph:=h[now]; {tmph保存未重新標號前now節點的高度} 122 dec(vh[tmph]); {高度為h[now]的節點數減一} 123 h[now]:=$ffff; {高度要取min(j)c[now,j]>0,則先賦值最大} 124 for i:=1 to n do 125 if (c[now,i]>f[now,i])and(h[now]>h[i]+1) then 126 h[now]:=h[i]+1; {更新標號的過程} 127 inc(vh[h[now]]); {新產生節點的高度記錄進去} 128 if vh[tmph]=0 then {GAP優化，如果存在間隙，則最大流已求出} 129 for i:=1 to n do 130 if (h[i]>tmph)and(h[i]<n) then {讓各個節點均抬高到n} 131 begin 132 dec(vh[h[i]]); 133 h[i]:=n; 134 inc(vh[n]); 135 end; {不能直接退出，否則會無限執行且不滿足流量平衡} 136 if (now<>s)and(now<>t) then 137 insect(now);{now經過PUSH過程已經不再活躍節點內了，且一定有盈余,但一定要保證now不是源，匯} 138 end; { ralable } 139 procedure main; 140 var 141 tmp : longint; 142 begin 143 while listsum<>0 do {當表中存在活躍節點時} 144 begin 145 tmp:=find(level); {找到最高標號點} 146 push(tmp); {推進} 147 if e[tmp]>0 then {如果推進后該節點還有盈余} 148 relable(tmp); {重新標號該節點} 149 end; 150 end; { main } 151 procedure print; 152 var 153 i : longint; 154 begin 155 flow:=0; 156 for i:=1 to n do {累加源的出流量} 157 inc(flow,f[s,i]); 158 writeln(flow); 159 end; { print } 160 begin 161 init; 162 bfs(); 163 previous; 164 main; 165 print; 166 end.

?

?

小結：

網絡流的最大流算法種類繁多，時間效率編程復雜度也不盡相同，對于不同的流網絡，選擇相應的算法，需要在不斷實踐中摸索，這也是一個菜鳥到大牛的必經之路。在一般題目中，選用Dinic是一個不錯的想法，但當我們發現網絡特別稠密時，FIFO的預留推進算法就要派上用場了，而時間比較緊但題目數據弱，我們甚至可以采用搜索找增廣路的算法。

提供最大流測試網址：http://hzoi.openjudge.cn/never/1003/

?

?

?????第三部分??最小費用最大流問題

?學習了網絡流的最大流算法，一定有一種十分興奮的感覺，那么，就讓你借著這股興奮勁兒，來學習這一章的最小費用流吧。

最小費用流有兩種經典的算法，一種是消圈算法，另一種則是最小費用路增廣算法。

第一種，消圈算法。如果在一個流網絡中求出了一個最大流，但對于一條增廣路上的某兩個點之間有負權路，那么這個流一定不是最小費用最大流，因為我們可以讓一部分流從這條最小費用路流過以減少費用，所以根據這個思想，可以先求出一個最大初始流，然后不斷地通過負圈分流以減少費用，直到流網絡中不存在負圈為止。

消圈算法的時間復雜度上限為O(nm^2cw),其中c是最大流量，w為非用最大值，而按特定的順序消圈的時間復雜度為O(nm^2logn)。這里的時間復雜度分析是按照用bellman-ford算法消圈得到的，用SPFA應該可以得到更優的實際運行時間。

第二種，最小費用路增廣算法。這里運用了貪心的思想，每次就直接去找s到t的最小費用路來增廣，這樣得到的結果一定是最小費用，實現較簡單，時間復雜度O(mnv)，v為最大流量。用SPFA效果極好，但鑒于SPFA的不確定性，有時為了保險，往往運用重新加權技術，具體實踐請通過網絡或其他途徑獲得。

最小費用流的東西并不多，事實上是使用最短路徑這種特殊的網絡流解決了普遍的網絡流問題，只要掌握好基礎，程序不難寫出。

1 View Code 2 program minflow(input,output); 3 var 4 f : array[0..501,0..501] of longint; 5 c : array[0..501,0..501] of longint; 6 min,pre,d : array[0..1000] of longint; 7 q : array[0..2000] of longint; 8 v : array[0..501] of boolean; 9 m,n,s,t : longint; 10 procedure init; 11 var 12 xx,yy,cc,dd : longint; 13 i : longint; 14 begin 15 readln(n,m); 16 fillchar(f,sizeof(f),63); 17 fillchar(c,sizeof(c),0); 18 for i:=1 to n do 19 f[i,i]:=0; 20 for i:=1 to m do 21 begin 22 readln(xx,yy,cc,dd); 23 f[xx,yy]:=dd; 24 c[xx,yy]:=cc; 25 f[yy,xx]:=-dd; 26 end; 27 s:=1; 28 t:=n; 29 end; { init } 30 function argument():boolean; 31 var 32 head,tail : longint; 33 i,now : longint; 34 begin 35 for i:=1 to n do 36 d[i]:=maxlongint>>2; 37 fillchar(v,sizeof(v),false); 38 fillchar(min,sizeof(min),63); 39 head:=0; 40 tail:=1; 41 q[1]:=s; 42 v[1]:=true; 43 d[1]:=0; 44 while head<tail do 45 begin 46 inc(head); 47 v[q[head]]:=false; 48 now:=q[head]; 49 for i:=1 to n do 50 if c[now,i]<>0 then 51 begin 52 if d[now]+f[now,i]<d[i] then 53 begin 54 d[i]:=d[now]+f[now,i]; 55 pre[i]:=now; 56 if c[now,i]<min[now] then 57 min[i]:=c[now,i] 58 else 59 min[i]:=min[now]; 60 if not v[i] then 61 begin 62 inc(tail); 63 q[tail]:=i; 64 v[i]:=true; 65 end; 66 end; 67 end; 68 end; 69 if d[t]=maxlongint>>2 then 70 exit(false); 71 now:=t; 72 while now<>s do 73 begin 74 dec(c[pre[now],now],min[t]); 75 inc(c[now,pre[now]],min[t]); 76 now:=pre[now]; 77 end; 78 end; { argument } 79 procedure main; 80 var 81 ans : longint; 82 begin 83 ans:=0; 84 while argument() do 85 inc(ans,min[t]*d[t]); 86 writeln(ans); 87 end; { main } 88 begin 89 init; 90 main; 91 end.

?

?

?? ? ? ? ??第四部分??網絡流算法的應用

一．??最大流問題。

一般情況下，比較裸的最大流幾乎不存在，網絡流這種東西考得就是你的構圖能力，要不然大家背一背基本算法就都滿分了，下面介紹一道比較典型的最大流問題。

???問題一：最小路徑覆蓋問題。

???題目鏈接：http://hzoi.openjudge.cn/never/1004/

???最小路徑覆蓋=|P|－最大匹配數

???而最大匹配數可以用匈牙利，也可以用最大流，而兩者在這特殊的圖中，效率是相同的，而一旦題目有一些變化，網絡流可以改改繼續用，而匈牙利的局限性較大。

???問題二：奶牛航班。

?? Usaco的賽題，以飛機上的座位作為流量限制，通過實際模型的構建，最終運用最大流算法解決，詳解可參考國家集訓隊論文，具體哪年的忘記了，囧。

??最大流實在難已以找到比較有意思的題目，下面進入應用最廣泛的最小費用流吧！

?

二.最小費用流問題（最大收益流問題）

這個問題的模型很多下面就此解析幾道例題。

???問題一：N方格取數

???在一個有m*n?個方格的棋盤中，每個方格中有一個正整數?，F要從方格中取數，使任意2?個數所在方格沒有公共邊，且取出的數的總和最大。

???解析：這是一個二分圖最大點權獨立集問題，就是找出圖中一些點，使得這些點之間沒有邊相連，這些點的權值之和最大。獨立集與覆蓋集是互補的，求最大點權獨立集可以轉化為求最小點權覆蓋集（最小點權支配集）。最小點權覆蓋集問題可以轉化為最小割問題解決。

???結論:最大點權獨立集?=?所有點權?-?最小點權覆蓋集?=?所有點權?-?最小割集?=?所有點權?-?網絡最大流。

???問題還有許多，可以參考網上的網絡流與線性規劃24題，里面題目比較全面（雖然好多根本用不到網絡流）。

最后再提一道題目，說一下最小割的轉化建模。

The last問題：黑手黨

題目大意：要用最少的人數來切斷從A到B的所有路徑，每個人只能切斷一條邊。

分析：顯然是一個從A到B的最小割問題，由最大流最小割定理，求A到B?的最大流即可。

結論：網絡流問題博大精深，難點在構圖，這是一種能力，需要逐漸培養。

?

總結：關于網絡流的介紹到這里也就結束了，但是網絡流絕不是僅僅這點東西的，由于個人水平問題，出錯或片面的地方還請大牛指正。

?

參考資料：

[1].國家集訓隊論文2007?王欣上，淺談基于分層思想的網絡流算法。

[2].國家集訓隊論文2002，江鵬，從一道題目的解法試壇網絡流的構造與算法。

[3].算法藝術與信息學競賽，劉汝佳，黃亮。

?

[轉]?http://www.cnblogs.com/neverforget/archive/2011/10/20/2210785.html

?

-----------

注：預留推進算法Gap優化：

若發現存在某個高度t<|V|，使得沒有任何點的高

? 度為t，則可以把所有高度在( t, |V| ]之間的點的高度

? 全部提升到|V|+1

總結

以上是生活随笔為你收集整理的浅谈网络流的基本算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。