Dinic演算法

『壹』 網路流的最大流演算法

1、augment path，直譯為「增廣路徑」，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個演算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個演算法必然會結束。
尋找通路的時候可以用DFS，BFS最短路等演算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上一個數量級。
增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個復雜得多的演算法，就是預推進演算法。
2、push label，直譯為「預推進」演算法。
3、壓入與重標記(Push-Relabel)演算法
除了用各種方法在剩餘網路中不斷找增廣路(augmenting)的Ford-Fulkerson系的演算法外，還有一種求最大流的演算法被稱為壓入與重標記(Push-Relabel)演算法。它的基本操作有：壓入，作用於一條邊，將邊的始點的預流盡可能多的壓向終點；重標記，作用於一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel系的演算法普遍要比Ford-Fulkerson系的演算法快，但是缺點是相對難以理解。
Relabel-to-Front使用一個鏈表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。演算法的主過程是：首先將源點出發的所有邊充滿，然後將除源和匯外的所有頂點保存在一個鏈表裡，從鏈表頭開始進行Discharge，如果完成後頂點的高度有所增加，則將這個頂點置於鏈表的頭部，對下一個頂點開始Discharge。
Relabel-to-Front演算法的時間復雜度是O(V^3)，還有一個叫Highest Label Preflow Push的演算法復雜度據說是O(V^2*E^0.5)。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的演算法是使用隊列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。
Push-Relabel類的演算法有一個名為gap heuristic的優化，就是當存在一個整數0<k<V，沒有任何頂點滿足h[v]=k時，對所有h[v]>k的頂點v做更新，若它小於V+1就置為V+1。
cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#;inttt,kase;intnn,m;intH[45],X[1004],P[1004],flow[1004],tot,cap[1005];intd[45];intS,T;voidadd(intx,inty,intz){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int>q;boolbfs(){memset(d,0,sizeof(d));d[S]=1;intx;q.push(S);while(!q.empty()){x=q.front();q.pop();for(inti=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}intdfs(intx,inta){if(x==T||a==0)returna;intf=a,tmp;for(inti=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;returnf-a;}intDinic(){intf=0;while(bfs())f+=dfs(S,inf);returnf;}intmain(){/**輸入過程省略**/intmaxflow=Dinic();printf(%d ,maxflow);return0;}

『貳』 sap演算法的演算法介紹

如果能讓每次尋找增廣路時的時間復雜度降下來，那麼就能C了，使用距離標號的最短增廣路演算法就是這樣的。所謂距離標號，就是某個點到匯點的最少的弧的數量（另外一種距離標號是從源點到該點的最少的弧的數量，本質上沒什麼區別）。設點i的標號為D[i]，那麼如果將滿足D[i]=D[j]+1的弧(i,j)叫做允許弧，且增廣時只走允許弧，那麼就可以達到「怎麼走都是最短路」的效果。每個點的初始標號可以在一開始用一次從匯點沿所有反向邊的BFS求出，實踐中可以初始設全部點的距離標號為0，問題就是如何在增廣過程中維護這個距離標號。
維護距離標號的方法是這樣的：當找增廣路過程中發現某點出發沒有允許弧時，將這個點的距離標號設為由它出發的所有弧的終點的距離標號的最小值加一。這種維護距離標號的方法的正確性我就不證了。由於距離標號的存在，由於「怎麼走都是最短路」，所以就可以採用DFS找增廣路，用一個棧保存當前路徑的弧即可。當某個點的距離標號被改變時，棧中指向它的那條弧肯定已經不是允許弧了，所以就讓它出棧，並繼續用棧頂的弧的端點增廣。還有一種在常數上有所優化的寫法是改變距離標號時把當前弧設為那條提供了最小標號的弧。當前弧的寫法之所以正確就在於任何時候我們都能保證在鄰接表中當前弧的前面肯定不存在允許弧。
還有一個常數優化是在每次找到路徑並增廣完畢之後不要將路徑中所有的頂點退棧，而是只將瓶頸邊以及之後的邊退棧，這是借鑒了Dinic演算法的思想。注意任何時候待增廣的「當前點」都應該是棧頂的點的終點。這的確只是一個常數優化，由於當前邊結構的存在，我們肯定可以在O(n)的時間內復原路徑中瓶頸邊之前的所有邊。

『叄』 請問求最大流的時間復雜度最小的演算法是哪一種

理論上是最高標號預流推進,英語縮寫HLPP
但是實現較復雜
實踐發現你把dinic和sap學了應該不會出先這兩種都過不去的程序設計題目,要注意sap的優化

『肆』 網路流之最大流，您只需判斷這個代碼是屬於哪一種最大流演算法即可。

Edmonds - Karp 演算法
最簡單的增廣路類演算法，每次用一個 BFS 尋找最短增廣路
while(1) 里前半部分的 for 循環就是 BFS 部分，隊列 que[] 輔助進行 BFS，找到的增廣路存在 pre[i] 中
if(!pre[sink])判斷是否存在可到達匯點的增廣路，不存在就跳出循環
後半部分 for 循環對找到的路徑進行增廣操作。

時間復雜度 O(VE^2)，行數雖少，但效率不是很高的演算法

最後說一句，這代碼風格太差了 = =，只考慮代碼長度完全不顧可讀性

參考資料是自己的 blog 呵呵

『伍』 數學建模網路流演算法重要嗎你們都用什麼演算法呢

1、蒙特卡羅演算法（該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，
同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法）
2、數據擬合、參數估計、插值等數據處理演算法（比賽中通常會遇到大量的數據需要處理，
而處理數據的關鍵就在於這些演算法，通常使用matlab作為工具）
3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題（建模競賽大多數問題屬於最優化問題，
很多時候這些問題可以用數學規劃演算法來描述，通常使用lindo、lingo軟體實現）
4、圖論演算法（這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，
涉及到圖論的問題可以用這些方法解決，需要認真准備）
5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法（這些演算法是演算法設計中比較常用的方法，很多場合可以用到競賽中）
6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法
（這些問題是用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，
但是演算法的實現比較困難，需慎重使用）
7、網格演算法和窮舉法（網格演算法和窮舉法都是暴力搜索最優點的演算法，在很多競賽題中有應用，
當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具）
8、一些連續離散化方法（很多問題都是實際來的，數據可以是連續的，而計算機只認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要的）
9、數值分析演算法（如果在比賽中採用高級語言進行編程的話，那一些數值分析中常用的演算法比
如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用）
10、圖象處理演算法（賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的，
這些圖形如何展示以及如何處理就是需要解決的問題，通常使用matlab進行處理）

『陸』 Dinic演算法的演算法介紹

1、根據殘量網路計算層次圖。
2、在層次圖中使用DFS進行增廣直到不存在增廣路。
3、重復以上步驟直到無法增廣。 ProgramDinic;TypeLx=Array[0..50]OfLongint;VarLu:Lx;A,B:Array[0..50]OfLx;D,Dist:LX;V,T:Array[0..50]OfBoolean;Head,Tail,Sum,Ans,X,Y,S,I,P,J,K,M,N:Longint;Q,C:Boolean;ProcereSpfa(S:Longint);VarI,J,Now,Sum:Longint;BeginFillchar(D,Sizeof(D),0);Fillchar(V,Sizeof(V),False);ForJ:=1ToNDoDist[J]:=MaxLongint;Dist[S]:=0;V[S]:=True;D[1]:=S;Head:=1;Tail:=1;WhileHead<=TailDoBeginNow:=D[Head];ForI:=1ToB[Now,0]DoifA[Now,B[Now,I]]>0thenIf(Dist[B[Now,I]]>Dist[Now]+1)ThenBeginDist[B[Now,I]]:=Dist[Now]+1;IfNotV[B[Now,I]]ThenBeginInc(Tail);D[Tail]:=B[Now,I];V[B[Now,I]]:=True;End;End;Inc(Head);End;End;ProcereDfs(X,D:Longint);VarI:Longint;BeginLu[D]:=X;T[X]:=True;IfX=NThenBeginC:=False;S:=D;End;ForI:=1ToNDoIf(A[X,I]>0)AndCAnd(NotT[I])And(Dist[X]+1=Dist[I])ThenDfs(I,D+1);End;ProcereExpand(L:Lx;Len:Longint);VarI,J,K:Longint;BeginK:=MaxLongint;ForI:=2ToLenDoIfK>A[L[I-1],L[I]]ThenK:=A[L[I-1],L[I]];Sum:=K;Writeln('K=',K);ForI:=2ToLenDoBeginDec(A[L[I-1],L[I]],K);Inc(A[L[I],L[I-1]],K);End;End;BeginRead(N,M);ForI:=1ToMDoBeginRead(X,Y,K);A[X,Y]:=K;Inc(B[X,0]);B[X,B[X,0]]:=Y;End;C:=False;WhileTrueDoBeginSpfa(1);ForI:=1ToNDoT[I]:=False;K:=MaxLongint;C:=True;Dfs(1,1);IfCThenBreak;Expand(Lu,S);Inc(Ans,Sum);End;Writeln(Ans);End.

『柒』 誰懂網路流演算法

1.Fort_Fulkerson演算法. 2.Edmonds_Karp演算法. 3.Push_Relabel 演算法 4.Relabel_to_Front演算法.

<<演算法藝術與信息學競賽>>上介紹了五種演算法.

1.Fort_Fulkerson演算法. 2.最短增廣路演算法. 3.使用距離標號的最短增廣路演算法. 4.預流推進演算法 5.最高標號的預流推進演算法.

<<實用演算法分析與程序設計>>上介紹了一種演算法:

1.Dinic演算法.

另外在網上又看見一些其它演算法:

1.SAP演算法. 2.pre_flow 演算法 3.FIFO pre_flow演算法 。。。 。。。

其實不少演算法說的都是同一個東西，只是名稱不一樣，現在總結如下:

1.Fort_Fulkerson演算法.

2.Edmonds_Karp演算法(最短增廣路演算法).-------------------O( n*m^2 )

3.SAP演算法(使用距離標號的最短增廣路演算法).--------------O( n^2*m )

4.Dinic演算法.------------------------------------------------------O( n^2*m )

5.Push_Relabel演算法(預流推進演算法).------------------------O( n^2*m )

6.FIFO Preflow_Push演算法.------------------------------------O( n^2*m)

7.Relabel_to_Front演算法.---------------------------------------O( n^3 )

8.Highest Label Preflow_push演算法.--------------------------O( n^2*m^1/2)

『捌』 cmd5x演算法是什麼意思

Dinic演算法（又稱Dinitz演算法）是一個在網路流中計算最大流的強多項式復雜度的演算法，設想由以色列（前蘇聯）的計算機科學家Yefim (Chaim) A. Dinitz在1970年提出。 演算法的時間復雜度類似於Edmonds–Karp演算法，其時間復雜度為，Dinic演算法與Edmonds–Karp演算法的不同之處在於它每輪演算法都選擇最短的可行路徑進行增廣。Dinic演算法中採用高度標號（level graph）以及阻塞流（blocking flow）實現其性能。