網路流(network-flows)是一種類比水流的解決問題方法，與線性規劃密切相關。網路流的理論和套用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網路流的分解與合成等新課題。網路流的套用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。
基本介紹
- 中文名：網路流
- 外文名：Network-flows
- 表達式：G=(V,E,F)
- 適用領域範圍：運籌學中的最最佳化問題
- 主要算法：預流推進，增廣路算法
- 套用學科：計算機科學
定義,最大流算法,最小費用算法,常用算法,網路算法,套用,
定義
圖論中的一種理論與方法，研究網路上的一類最最佳化問題 。1955年 ，T.E.哈里斯在研究鐵路最大通量時首先提出在一個給定的網路上尋求兩點間最大運輸量的問題。1956年，L.R. 福特和 D.R. 富爾克森等人給出了解決這類問題的算法，從而建立了網路流理論。所謂網路或容量網路指的是一個連通的賦權有向圖 D= （V、E、C） ， 其中V 是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網路上的流就是由起點流向終點的可行流，這是定義在網路上的非負函式，它一方面受到容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。如果把下圖看作一個公路網，頂點v1…v6表示6座城鎮，每條邊上的權數表示兩城鎮間的公路長度。現在要問 ：若從起點v1將物資運送到終點v6去 ，應選擇那條路線才能使總運輸距離最短?這樣一類問題稱為最短路問題 。 如果把上圖看作一個輸油管道網 ， v1 表示傳送點，v6表示接收點，其他點表示中轉站 ，各邊的權數表示該段管道的最大輸送量。現在要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大。這樣的問題稱為最大流問題。
最大流理論是由福特和富爾克森於 1956 年創立的 ，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善 。最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論套用的新途徑。
假設G(V,E) 是一個有限的有向圖，它的每條邊(u,v)∈E都有一個非負值實數的容量c(u,v) 。如果(u,v)不屬於E，我們假設c(u,v) = 0 。我們區別兩個頂點：一個源點s和一個匯點t。一道網路流是一個對於所有結點u和v都有以下特性的實數函式f:V×V→R
容量限制 (Capacity Constraints): | f(u,v)≤c(u,v)一條邊的流不能超過它的容量。 |
斜對稱 (Skew Symmetry): | f(u,v)=-f(v,u)由u到v的淨流必須是由v到u的淨流的相反（參考例子）。（既然要看網路流，這是一定要知道的） |
流守恆 (Flow Conservation): | 除非u=s或u=t，否則Σ（w∈V）f(u,w)=0 一結點的淨流是零，除了“製造”流的源點和“消耗”流的匯點。 |
注意f(u,v) 是由u到v的淨流。如果該圖代表一個實質的網路，由u到v有 4 單位的實際流及由v到u有 3 單位的實際流，那么f(u,v) = 1 及f(v,u) = − 1。
邊的剩餘容量 (Residual Capacity)是cf(u,v) =c(u,v)−f(u,v)。這定義了以Gf(V,Ef)表示的剩餘網路 (Residual Network)，它顯示可用的容量的多少。留意就算在原網路中由u到v沒有邊，在剩餘網路乃可能有由u到v的邊。因為相反方向的流抵消，減少由v到u的流等於增加由u到v的流。擴張路徑 (Augmenting Path)是一條路徑 (u1,u2...uk)，而u1 =s、uk=t及cf(ui,ui+ 1) > 0，這表示沿這條路徑傳送更多流是可能的。
最大流算法
1、augment path，直譯為“增廣路徑”，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜尋出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。
增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個複雜得多的算法，就是預推進算法。
2、push label，直譯為“預推進”算法。
3、壓入與重標記(Push-Relabel)算法
除了用各種方法在剩餘網路中不斷找增廣路(augmenting)的Ford-Fulkerson系的算法外，還有一種求最大流的算法被稱為壓入與重標記(Push-Relabel)算法。它的基本操作有：壓入，作用於一條邊，將邊的始點的預流儘可能多的壓向終點；重標記，作用於一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺點是相對難以理解。
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>#define inf 0x7fffffffusing namespace std;int tt,kase;int nn,m;int H[45],X[1004],P[1004],flow[1004],tot,cap[1005];int d[45];int S,T;void add(int x,int y,int z){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int> q;bool bfs(){memset(d,0,sizeof(d));d[S]=1; int x;q.push(S);while(!q.empty()){x=q.front();q.pop();for(int i=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}return d[T];}int dfs(int x,int a){if(x==T||a==0)return a;int f=a,tmp;for(int i=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;return f-a;}int Dinic(){int f=0;while(bfs())f+=dfs(S,inf);return f;}int main(){/**輸入過程省略**/int maxflow=Dinic();printf("%d\n",maxflow);return 0;}最小費用算法
常用算法
一．Ford和Fulkerson迭加算法
基本思路：把各條弧上單位流量的費用看成某種長度，用求解最短路問題的方法確定一條自V1至Vn的最短路；在將這條最短路作為可擴充路，用求解最大流問題的方法將其上的流量增至最大可能值；而這條最短路上的流量增加後，其上各條弧的單位流量的費用要重新確定，如此多次疊代，最終得到最小費用最大流。
迭加算法：
1) 給定目標流量F或∞，給定最小費用的初始可行流=0。
2) 若V(f)=F，停止，f為最小費用流；否則轉(3)。
3) 構造相應的新的費用有向圖W(fij)，在W(fij)尋找Vs到Vt的最小費用有向路P(最短路)，沿P增加流f的流量直到F，轉(2)；若不存在從Vs到Vt的最小費用的有向路P，停止。f就是最小費用最大流。
最大流問題僅注意網路流的流通能力，沒有考慮流通的費用。實際上費用因素是很重要的。例如在交通運輸問題中，往往要求在完成運輸任務的前提下，尋求一個使總運輸費用最省的運輸方案，這就是最小費用流問題。如果只考慮單位貨物的運輸費用，那么這個問題就變成最短路問題。由此可見，最短路問題是最小費用流問題的基礎。現已有一系列求最短路的成功方法。最小費用流(或最小費用最大流)問題 ，可以交替使用求解最大流和最短路兩種方法，通過疊代得到解決。
二．圈算法：
1) 利用Ford和Fulkson標號算法找出流量為F(<=最大流)的流f。
2) 構造f對應的調整容量的流網路N'(f)。
3) 搜尋N'(f)中的負費用有向圖C(Floyd算法)，若沒有則停止，否則轉(4)。
4) 在C上找出最大的循環流，並加到N上去，同時修改N'(F)中C的容量，轉(3)。
三. ZKW費用流
費用流是網路流的一個很重要的組成部分，也是非常有用的一種圖論模型，關於費用流的算法，流傳比較廣的主要是消圈和增廣路算法，而近來炒得沸沸揚揚的ZKW算法也是一種非常優秀的算法，這裡我就談談我對此算法的一些理解。
此算法是由ZKW大牛創立，主要思想仍然是找增廣路，只是有了一些最佳化在裡邊。原來我們找增廣路主要是依靠最短路算法，如SPFA。因此此算法的時間複雜度主要就取決於增廣的次數和每次增廣的耗費。由於每一次找增廣路是都是重新算一遍，這樣似乎顯得有些浪費，如果我們能夠縮短找增廣路的時間，那必定會大大地最佳化算法。
值得注意的是，在尋求最短路得過程中，設dis[i]為i到起點的距離，對於每一條由i引向j的邊，必有dis[j]<=dis[i]+map[i][j]；既然滿足這樣的恆等式，我們就可以借用KM算法的調整思想來尋求最短路，每次只走dis[j]=dis[i]+map[i][j]的路徑，一旦不存在到達終點的路徑，就掃描每一條邊，找到最小的距離增加值，使得有至少一條新邊被加入相等子圖。
算法流程如下：
1.將dis數組清零，表示當前的相等子圖內只有起點。
（如果存在負權邊，必須要用spfa跑一遍，初始化出dis數組，下面的第二題就是這樣的例子）。
2.深搜，如果到達終點，全部回退更改流量，再進行步驟2；否則，轉3。
3.修改dis的值，如果無法修改，結束程式，已經找到的答案，反之轉2。
有上下界
上面討論的網路流都只對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧<Vi, Vj>加上一個下界限制Aij (即必須滿足Aij≤fij)。
弧上數字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。
網路算法
一、網路流的基本概念
先來看一個實例。
現在想將一些物資從S運抵T，必須經過一些中轉站。連線中轉站的是公路，每條公路都有最大運載量。如下圖：
每條弧代表一條公路，弧上的數表示該公路的最大運載量。最多能將多少貨物從S運抵T？
這是一個典型的網路流模型。為了解答此題，我們先了解網路流的有關定義和概念。
若有向圖G=(V,E)滿足下列條件：
1、 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發點。
2、 有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。
3、 每一條弧都有非負數，叫做該邊的容量。邊(vi, vj)的容量用cij表示。
則稱之為網路流圖，記為G = (V, E, C)
可行流
對於網路流圖G，每一條弧(i,j)都給定一個非負數fij，這一組數滿足下列三條件時稱為這網路的可行流，用f表示它。
(1) 每一條弧(i,j)有fij≤cij。
(2) 除源點S和匯點T以外的所有的點vi，恆有：
該等式說明中間點vi的流量守恆，輸入與輸出量相等。
(3) 對於源點S和匯點T有：
這裡V(f)表示該可行流f的流量。
例如對圖5-1而言，它的一個可行流如下：
流量V(f) = 5。
可改進路
給定一個可行流f=。若fij = cij，稱<vi, vj>為飽和弧；否則稱<vi, vj>為非飽和弧。若fij = 0，稱<vi, vj>為零流弧；否則稱<vi, vj>為非零流弧。
定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。
譬如在圖5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
給定一個可行流f，P是從S到T的一條道路，如果滿足：
那么就稱P是f的一條可改進路。（有些書上又稱：可增廣軌）之所以稱作“可改進”，是因為可改進路上弧的流量通過一定的規則修改，可以令整個流量放大。具體方法下一節會重點介紹，此不贅述。
割切
要解決網路最大流問題，必須先學習割切的概念和有關知識。
G = (V, E, C)是已知的網路流圖，設U是V的一個子集，W = V\U，滿足S U，T W。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。
對於弧尾在U，弧頭在W的弧所構成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W）。
定理：對於已知的網路流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V(f) ≤ C(U, W)。
通俗簡明的講：“最大流小於等於任意割”。這是“流理論”里最基礎最重要的定理。整個“流”的理論系統都是在這個定理上建立起來的，必須特別重視。
網路流、可改進路、割切都是基礎的概念，應該紮實掌握。它們三者之間乍一看似乎風馬牛不相干，其實內在聯繫是十分緊密的。
二、求最大流
何謂最大流？首先它必須是一個可行流；其次，它的流量必須達到最大。這樣的流就稱為最大流。譬如對圖5-1而言，它的最大流如下：
下面探討如何求得最大流。
在定義“可改進路”概念時，提到可以通過一定規則修改“可改進路”上弧的流量，可以使得總流量放大。下面我們就具體看一看是什麼“規則”。
對可改進路P上的弧<vi, vj>，分為兩種情況討論：
第一種情況：<vi, vj>∈P+，可以令fij增加一個常數delta。必須滿足fij + delta ≤ cij，即delta ≤ cij – fij。
第二種情況：<vi, vj>∈P-，可以令fij減少一個常數delta。必須滿足fij - delta ≥ 0，即delta ≤ fij
根據以上分析可以得出delta的計算公式：
因為P+的每條弧都是非飽和弧，P-的每條弧都是非零流弧，所以delta > 0。
容易證明，按照如此規則修正流量，既可以使所有中間點都滿足“流量守恆”（即輸入量等於輸出量），又可以使得總的流量有所增加（因為delta > 0）。
因此我們對於任意的可行流f，只要在f中能找到可改進路，那么必然可以將f改造成為流量更大的一個可行流。我們要求的是最大流，現在的問題是：倘若在f中找不到可改進路，是不是f就一定是最大流呢？
答案是肯定的。下面我們給出證明。
定理1 ：可行流f是最大流的充分必要條件是：f中不存在可改進路。
證明：
首先證明必要性：已知最大流f，求證f中不存在可改進路。
若最大流f中存在可改進路P，那么可以根據一定規則（詳見上文）修改P中弧的流量。可以將f的流量放大，這與f是最大流矛盾。故必要性得證。
再證明充分性：已知流f，並且f中不存在可改進路，求證f是最大流。
我們定義頂點集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，則y∈U;
若x∈U，且fyx>0，則y∈U。
（這實際上就是可改進路的構造規則）
（c） W = V \ U。
由於f中不存在可改進路，所以T∈W；又S∈U，所以U、W是一個割切（U, W）。
按照U的定義，若x∈U，y∈W，則fxy = cxy。若x∈W，y∈U，則fxy = 0。
所以，又因 v(f)≤C(U,W)
所以f是最大流。得證。
根據充分性證明中的有關結論，我們可以得到另外一條重要定理：
最大流最小割定理：最大流等於最小割，即max V(f) = min C(U, W)。
至此，我們可以輕鬆設計出求最大流的算法：
step 1. 令所有弧的流量為0，從而構造一個流量為0的可行流f（稱作零流）。
step 2. 若f中找不到可改進路則轉step 5；否則找到任意一條可改進路P。
step 3. 根據P求delta。
step 4. 以delta為改進量，更新可行流f。轉step 2。
step 5. 算法結束。此時的f即為最大流。
三、最小費用最大流
1．問題的模型
流最重要的套用是儘可能多的分流物資，這也就是我們已經研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的餘地，費用的因素就自然參與到決策中來。
一般的，設有帶費用的網路流圖G = (V, E, C, W)，每條弧<Vi, Vj>對應兩個非負整數Cij、Wij，表示該弧的容量和費用。若流f滿足：
(a) 流量V(f)最大。
(b) 滿足a的前提下，流的費用Cost(f) = 最小。
就稱f是網路流圖G的最小費用最大流。
2．算法設計
我們模仿求最大流的算法，找可改進路來求最小費用最大流。
設P是流f的可改進路，定義 為P的費用（為什麼如此定義？）。如果P是關於f的可改進路中費用最小的，就稱P是f的最小費用可改進路。
求最小費用最大流的基本思想是貪心法。即：對於流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。
算法可描述為：
step 1. 令f為零流。
step 2. 若無可改進路，轉step 5；否則找到最小費用可改進路，設為P。
step 3. 根據P求delta（改進量）。
step 4. 放大f。轉step 2。
step 5. 算法結束。此時的f即最小費用最大流。
至於算法的正確性，可以從理論上證明。讀者可自己思考或查閱有關運籌學資料。
3．最小費用可改進路的求解
求“最小費用可改進路”是求最小費用最大流算法的關鍵之所在，下面我們探討求解的方法。
設帶費用的網路流圖G = (V, E, C, W)，它的一個可行流是f。我們構造帶權有向圖B = (V’, E’)，其中：
1、 V’ = V。
2、 若<Vi, Vj>∈E，fij<Cij，那么<Vi, Vj>∈E’，權為Wij。
若<Vi, Vj>∈E，fij>0，那么<Vj, Vi>∈E’，權為-Wij。
顯然，B中從S到T的每一條道路都對應關於f的一條可改進路；反之，關於f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關係。
故若B中不存在從S到T的路徑，則f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路。
現在的問題變成：給定帶權有向圖B = (V’, E’)，求從S到T的一條最短路徑。
考慮到圖中存在權值為負數的弧，不能採用Dijkstra算法；Floyd算法的效率又不盡如人意——所以，這裡採用一種折衷的算法：疊代法。
設Short[k]表示從S到k頂點的最短路徑長度；從S到頂點k的最短路徑中，頂點k的前趨記為Last[k]。那么疊代算法描述如下：（為了便於描述，令n = |V’|，S的編號為0，T的編號為n+1）
step 1. 令Short[k] +∞（1≤k≤n+1），Short[0] 0。
step 2. 遍歷每一條弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，則令Short[j] Short[k] + <k, j>，同時Last[j] k。倘不存在任何一條弧滿足此條件則轉step 4。
step 3. 轉step 2.
step 4. 算法結束。若Short[n + 1]= +∞，則不存在從S到T的路徑；否則可以根據Last記錄的有關信息得到最短路徑。
一次疊代算法的時間複雜度為O(kn2)，其中k是一個不大於n的變數。在費用流的求解過程中，k大部分情況下都遠小於n。
4．思維發散與探索
1）可改進路費用：“遞增！遞增？”
設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那么會不會有p1≤p2≤p3≤……≤pk呢？
2）疊代法：“小心死循環！嘿嘿……”
疊代法會出現死循環嗎？也就是說，構造的帶權有向圖B中會存在負迴路嗎？
3）費用：“你在乎我是負數嗎？”
網路流圖中的費用可以小於零嗎？
4）容量：“我管的可不僅是弧。”
網路流圖中的“容量”都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？
5．C++代碼實現
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;int H[105],X[40005],P[40005],from[40005],flow[40005],cost[40005],tot;inline void add(int x,int y,int z,int k){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;from[tot]=x;cost[tot]=k;}int f,c;int n,m;int S,T;int d[105],a[105],p[105];struct N{int x,w;friend bool operator < (N a,N b){return a.w>b.w;}N(int a=0,int b=0){x=a,w=b;}};priority_queue<N>q;bool spfa(){memset(d,0x3f,sizeof(d));d[S]=0;a[S]=inf;p[S]=0;int x;q.push(N(S,0));while(!q.empty()){x=q.top().x;q.pop();if(x==T)continue;for(int i=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]>d[x]+cost[i]){d[P[i]]=d[x]+cost[i];a[P[i]]=min(a[x],flow[i]);p[P[i]]=i;q.push(N(P[i],d[P[i]]));}}while(!q.empty()&&d[q.top().x]!=q.top().w)q.pop();}if(d[T]==inf)return 0;f+=a[T];c+=a[T]*d[T];x=T;while(x!=S){flow[p[x]]-=a[T];flow[p[x]^1]+=a[T];x=from[p[x]];}return 1;}int main(){#ifdef LOCALfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifInput();while(spfa());maxflow=f,mincost=c;return 0;}四、有上下界的最大流
上面討論的網路流都只對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧<Vi, Vj>加上一個下界限制Aij（即必須滿足Aij≤fij）。
那么有上下界的網路最大流怎么求呢？
一種自然的想法是去掉下界，將其轉化為只含上界的網路流圖。這種美好的願望是可以實現的。具體方法如下：
設原網路流圖為G = (V, E, C, A)，構造不含下界的網路流圖G’ = (V’, E’, C’)：
1、 V’ = V∪{S’, T’}
2、 對每個頂點x，令 ，若h-(x)≠0，就添加一條弧<S’, x>，其上界為h-(x)。
3、 對每個頂點x，令 ，若h+(x)≠0，就添加一條弧<x, T’>，其上界為h+(x)。
4、 對於任何<Vi, Vj>∈E，都有<Vi, Vj>∈E’，其上界C’ij = Cij – Aij。
5、 新增<T, S>∈E’，其上界CTS = +∞。
在G’中以S’為源點、T’為匯點求得最大流f’。若f’中從S’發出的任意一條弧是非飽和弧，則原網路流圖沒有可行流。否則可得原圖的一個可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正確性很容易證明，留給讀者完成）
然後再求可改進路（反向弧<Vi, Vj>必須滿足fij≥Aij，而非fij≥0），不斷放大f，直到求出最大流。
我們看到，上幾節所討論的一種可行網路流實際上是{Aij = 0}的一種特殊網路流，這裡提出的模型更一般化了。解決一般化的複雜問題，我們採取的思路是將其轉化為特殊的簡單問題，加以研究、推廣，進而解決。這是一種重要的基本思想：化歸——簡單有效。基於這種思想，請讀者自行思考解決：
1、 有上下界的最小流。
2、 有上下界的最小費用最大流。
五、多源點、多匯點的最大流
已知網路流圖有n個源點S1、S2、……、Sn，m個匯點T1、T2、……、Tm，，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。
它的解決很簡單：
1、 增設一個“超級源”S’，對每個源點Si，新增弧<S’, Si>，容量為無窮大。
2、 增設一個“超級匯”T’，對每個匯點Ti，新增弧<Ti, T’>，容量為無窮大。
3、 以S’為源點、T’為匯點求最大流f。
4、 將f中的S’和T’去掉，即為原圖的最大流。
算法正確性顯然。
六、頂點有容量限制的最大流
上一節已經提出了這個問題，即對於進出每個頂點的流量也規定一個上限，這樣的最大流如何求？
既然我們已經解決了“邊限制”問題，現在何不把“點限制”問題轉化為“邊限制”呢？具體辦法如下：
1、 對除源點和匯點之外的每個頂點i拆分成兩個頂點i’和i’’。新增一條弧<i’, i’’>，其容量為點i的流量限制。
2、 對於原圖中的弧<i, j>，我們將其變換成<i’’, j’>。
3、 對變換後的圖求最大流即可。
這裡我們又一次運用到了化歸的思想：將未知的“點限制”問題轉化為已知的“邊限制”問題。
七、網路流與二部圖的匹配
{二部圖和匹配的定義可參見本書專門介紹二部圖匹配的章節}
設二部圖為G = (X, Y, E)。
增設點S’，對於所有i∈X，新增弧<S’, Xi>，容量為1；增設點T’，對於所有i∈Y，新增一條弧<Yi, T’>，容量也為1。原圖中所有的弧予以保留，容量均為+∞。對新構造出來的網路流圖以S’為源點、T’為匯點求最大流：流量即為最大匹配數；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一條匹配邊。
二部圖最大匹配問題解決
那么二部圖的最佳匹配問題又如何？
仍然按照上述方法構圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然後以S’為源點、T’為匯點求最小費用最大流即可。最大流的費用即為原二部圖最佳匹配的費用。
網路套用
將一連串的水管繪畫成一個網路。每條水管有一特定的闊度，因此只可以保持一特定的水流量。當任何水管匯合，流入匯流點的總水量必須等於流出的水量，否則我們會很快地缺水，或者我們會團積水。我們有一個作為源點的入水口，和一個作為匯點的出水口。一道流便是一條由源點到匯點而使從出水口流出的總水量一致的可能路徑。直觀地，一個網路的總流量是水從出口流出的速率。
流可以關於在交通網路上的人或物質，或電力分配系統上的電力。對於任何這樣的實物網路，進入任何中途結點的流需要等於離開那結點的流。Bollobás以基爾霍夫電流定律描繪這限制的特性，同時較遲的作者（即 Chartrand）提及它在某些守恆方程的普遍化。
在生態學中也可找到流網路的套用：當考慮在食物網中不同組織之間養料及能量的流，流網路便自然地產生。與這些網路有聯繋的數學問題和那些液體流或交通流網路中所產生的難題有很大分別。由 Robert Ulanowicz 及其他人發展的生態系統網路分析領域包含使用資訊理論及熱力學的概念去研究這些網路隨時間的演變。
