Flow Network

把一張圖想成是水流管線圖。圖上的邊想成是水管：邊的權重想成是水管的容量上限（容量下限預設為零），有向邊僅允許單向流動，無向邊得同時雙向流動。圖上的點想成是水管的接合點，並附有控制水流流向與流量的機器：點的權重想成是接合處的容量上限（容量下限預設為零），但是大家一般都不考慮點的權重。

每一條管線的流量數值與容量上限數值，以一斜線區隔，標記於圖上各條邊，方便觀看。水流流動時必須遵守各條管線的容量限制，不得有逾越容量限制之情事。流量數值與容量上限數值一定是正值或零，不得為負值。

在這張水流管線圖當中，水流流速是穩定的、是源源不絕的，有變化的只有水流流向與流量。因此，水流流動時，只要關心各條管線的方向限制和容量限制就可以了。

當一張圖專門用於水流流動時，則可稱之為Flow Network，中譯為「流網路」。

「流網路」只有容量資訊，沒有流量資訊。

s-t Flow

在圖上選定一個源點（source，標記為s）和一個匯點（sink，標記為t），源點灌水，匯點泄水，並控制水流從源點流至匯點，中途不得滲漏、不得淤滯。

s-t Flow以下簡稱為「流」。一個流便是由源點經管線至匯點的水流。一個流的流量，即是源點灌入的水流流量，同時也是匯點泄出的水流流量。

「流」只有流量資訊，沒有容量資訊。

Maximum s-t Flow

「最大流」。給定一張圖，以及給定一個源點與一個匯點，所有可能的Flow當中，流量最大者便是Maximum Flow，可能會有許多個。

在源點一口氣灌入大量的水，藉由調整各條管線的流量與流向，讓匯點泄出的流量最多。

Minimum s-t Flow

「最小流」。一滴水都不流，管線裡都沒水，就是Min-Flow，流量為零。大家應該都懂，所以就討論到這裡了。

圖例：不屬於流的玩意

水流流到無法流動的地方，水流淤滯而無法流至匯點，不能稱作流。

圖例：合流、分流、交流

水流可以在任何點上合流、分流、交流──簡單地來說，就是每個點之中，流入與流出的水量要相等，至於要怎麼分合都無所謂。

圖例：產生迴圈的流

產生迴圈的流會佔據管線容量，令流量難以再增加，是一種浪費。

圖例：源點與匯點在一起的流

感情很好的兩個點，一般視作內地裡波濤洶湧，表面上流量為零。

多個源點變成一個源點、多個匯點變成一個匯點

先前都只討論一個源點和一個匯點的原因，其實是因為多個源點可以轉化成一個源點、多個匯點可以轉化成一個匯點。當圖上有多個源點時，就在圖上新增一個超級源點，連向這些源點，邊的容量都設定為無限大。如此一來，就可以只留下一個超級源點，並取消原本的源點了。匯點的道理亦同。

因此，在s-t Flow當中，多個源點和多個匯點可以改為一個源點和一個匯點，最後只討論一個源點和一個匯點就可以了。事情也變簡單多了。

點的容量變成邊的容量

先前提到大家一般不考慮點的容量，其實是因為點的容量可以轉化為邊的容量。把P點改成兩個點Pin和Pout，原先連到P點的邊變成連到Pin，由P點連出的邊變成由Pout連出，P點的容量則由一條Pin到Pout的邊來取代之。

因此，在s-t Flow當中，點的容量可以改為邊的容量，最後只要考慮邊的容量就行了。只考慮邊的容量，事情也變簡單多了。

多重的邊變成單獨的邊

無向圖中，當兩點之間有多重的邊，就可以加總這些邊的容量限制，合併成單獨的邊；有向圖中，當一點到另一點有多重的邊，就可以加總這些邊的容量限制，合併成單獨的邊。

因此，在s-t Flow當中，多重的邊可以改為單獨的邊，最後只討論「無向圖：兩點間僅有一條邊、有向圖：一點到另一點僅有一條邊」就可以了。事情也變簡單多了。

來回水流變成單向水流

兩點之間，兩條方向相反的有向邊，等量減少來向與回向的水流，不會影響總流量，也不會違背規則。

因此，在s-t Flow當中，來回水流可以變成單向水流，最後只要從中選擇一條邊來流動就可以了。事情也變簡單多了。

無向邊變成有向邊

無向邊得同時雙向流動。一條無向邊可以改為兩條方向相反的有向邊，可是必須共用容量。

由於來回水流可以變成單向水流，所以上述兩條方向相反的有向邊，其實不必共用容量，宛如普通的有向邊。

因此，在s-t Flow當中，一條無向邊可以變成兩條方向相反的有向邊，最後只討論有向邊就可以了。事情也變簡單多了。

一條涓流的流量與瓶頸

水從源點流至匯點，中途不會滲漏、不會淤滯。一條由源點流至匯點的小小涓流，其流動路徑當中，每一條邊的流量，都會是小小涓流的流量。

水流流動時要符合管線容量限制。一條由源點流至匯點的小小涓流，其流量的瓶頸，會是流動路徑當中，容量上限最低的一條邊。

一個流的總流量與瓶頸（一）

水從源點流至匯點，中途不會滲漏、不會淤滯。現在把圖上的點，依地理位置劃分作兩區，一區鄰近源點，另一區鄰近匯點──一個從源點流至匯點的流，「由源點流至匯點的總流量」會等於「由源點區流入到匯點區的總流量」減去「由匯點區流回到源點區的總流量」。無論是哪一種分區方式，都有這種性質。

水流流動時要符合管線容量限制。一個從源點流至匯點的流，「由源點區流入到匯點區的總流量」會小於等於「由源點區橫跨到匯點區的管線總容量」。反方向亦同。

也就是說，一個從源點流至匯點的流，其總流量的瓶頸，會出現在「由源點區橫跨到匯點區的管線總容量」最低的一種分區方式。

一個流的總流量與瓶頸（二）

【讀者若不懂s-t Cut，請見本站文件「Cut」。】

方才的分兩區方式有點籠統，很難定義誰鄰近源點，誰鄰近匯點，因此計算學家嘗試以s-t Cut來取代方才的說法，希望藉由s-t Cut把事情說得更嚴謹一些。然而事情也稍微變得複雜了。

水從源點流至匯點，中途不會滲漏、不會淤滯。現在把圖上的點，利用s-t Cut的概念劃分作兩側，一側包含源點，另一側包含匯點──一個從源點流至匯點的流，「由源點流至匯點的總流量」會等於「由源點側流入到匯點側的總流量」減去「由匯點側流回到源點側的總流量」。無論是哪一種劃分方式，都有這種性質。

水流流動時要符合管線容量限制。一個從源點流至匯點的流，「由源點側流入到匯點側的總流量」會小於等於「由源點側橫跨到匯點側的管線總容量」。反方向亦同。

也就是說，一個從源點流至匯點的流，其總流量的瓶頸，會出現在「由源點側橫跨到匯點側的管線總容量」最低的一種分區方式。也就是容量的Minimum s-t Cut。

Max-Flow Min-Cut Theorem

「最大流最小割定理」其實就是談瓶頸。「網路流量的最大s-t流」等於「管線容量的最小s-t割」，管線若還有空間，就儘量增加流量，直到遇到瓶頸，瓶頸會出現在容量的最小s-t割。

打個比方來說，在一個裝水的塑膠袋底部戳洞，水就會流出來；戳越多洞，水就流出的越多。這表示水一旦有隙可乘，就一定會源源而來、滔滔而至，乃增加流量。水一旦無隙可乘，流量達到上限，此刻就是最大流了。

要找最大流，可以運用「最大流最小割定理」的概念，讓水流不停地鑽空隙流至匯點，當無法再找到空隙時，就是極限了，就是最大流了。

若只找最大流流量，則可以運用求最小s-t割的演算法，計算管線容量的最小s-t割的權重，即是最大s-t流流量。

用途

給定一張圖，並給定源點、匯點，找出其中一個最大流。

Flow Decomposition

一個流是由許多條小小涓流逐漸聚集而成的。我們可以用一條一條的小小涓流，累積出最大流。

溯洄沖減
【註：此概念目前尚未有專有名詞】

然而有些涓流的路徑不理想，浪費了管線空間。有鑒於此，演算法作者設計了一個手法：溯洄沖減。流出第一條涓流之後，第二條涓流可以溯洄上一條流的部份路段，然後到達匯點。正流與逆流相互沖減的結果，使得相互交織的兩條涓流，成為兩條獨立的涓流。如此一來，就算涓流的路徑不理想，之後仍可靠溯洄沖減來調整路徑。

【註：涓流、溯洄、沖減這三個詞，是初次使用。我查字典後，覺得意義相近，而選用的。而且它們都是水字旁！】

溯洄沖減的時候，可以選擇水量多寡和路線位置，藉以調整成不同的流。

溯洄沖減的概念可以用於許多地方。這裡列出一些相關問題，供各位練習。

UVa 10806 10380

Residual Network

每次增加一條小小涓流，都要時時刻刻遵守各條管線的容量限制。管線要有剩餘空間，或者管線有溯洄沖減的機會，涓流才能流過管線。

一個便捷的整合方式是：管線的剩餘空間、再加上可供溯洄沖減的水量，稱作「剩餘容量Residual Capacity」；所有管線的剩餘容量，整體視作一張圖，稱作「剩餘網路Residual Network」。

如此一來，涓流要進行流動，只要參考剩餘網路，遵守各條管線的剩餘容量限制就可以了。

剩餘網路是一個高度抽象概念，為的是整合涓流流動的容量限制。實作程式碼時，可以直接建立一個剩餘網路的資料結構，隨時利用容量與剩餘容量來計算流量。

Augmenting Path

「擴充路徑」，剩餘網路上面一條由源點到匯點的路徑。換個角度想，把握管線的剩餘空間，把握溯洄沖減，找出一條由源點到匯點的小小涓流路徑，就是一條擴充路徑。

擴充路徑是一條可以擴充總流量的路徑，擴充的流量可多可少，一般來說流量越多越好，到達瓶頸最好，能較快達到最大流。

擴充路徑的長度範圍是1到V-1（長度為0表示源點與匯點重疊）。當一條擴充路徑超過V-1條邊，則會形成浪費管線容量的迴圈，此時應消除迴圈之後，才來做為擴充路徑。

演算法

不斷找擴充路徑，並擴充流量。直到沒有擴充路徑為止。

所有擴充路徑總合起來，就是最大流。
所有擴充路徑的流量總和，就是最大流流量。

擴充路徑要怎麼找都可以，
不一樣的擴充路徑有機會產生不一樣的最大流。

還找得到擴充路徑：
表示目前不是最大流，因為藉由擴充路徑，還可以再增加總流量。

找不到擴充路徑：
表示源點往匯點方向的一些關鍵管線已經沒有剩餘容量。沒有剩餘容量則表示：
甲、管線沒有剩餘空間（或根本沒有管線），也就是遭遇瓶頸。
乙、不能溯洄沖減。
根據最大流最小割定理，遭遇瓶頸時即是最大流。
【註：這部分的證明有漏洞。沒有考慮到形成迴圈的涓流。】

這個演算法的絕妙之處，是導入了溯洄沖減的機制，藉以調整流動路徑；然後把溯洄沖減併入了容量限制的思維，創立剩餘網路、擴充路徑等抽象概念；最後返回到最大流最小割定理，間接證明了溯洄沖減無論在什麼情況下，都能調整好流動路徑，找出最大流──調校水流的本質，就是剩餘網路。

另外可以發現，在整個過程當中，所有管線的剩餘容量的總和是固定不變的──只是源點往匯點方向的剩餘容量越來越少，匯點往源點方向的剩餘容量越來越多。整個過程可以看作是在調整剩餘網路的勢力走向──每次以擴充路徑擴充流量後，正方向會減少對應的剩餘容量，逆方向會增加對應的剩餘容量，源點與匯點之間的勢力差距越來越大。

時間複雜度

找一條擴充路徑，等同一次Graph Traversal的時間。

最差情況下，擴充路徑流量通通都是1，共找到F條，F是最大流的流量。

圖的資料結構使用Adjacency Matrix，便是O(V²F)；圖的資料結構使用Adjacency Lists，便是O((V+E)F)，通常簡單寫成O(EF)。

如何記錄容量、流量、剩餘容量

為了實現溯洄沖減的概念，要是兩點之間只有單獨一條有向邊，就添配一條反向邊，讓雙向都有邊；要是兩點之間已經是兩條方向相反的有向邊，就不必更動；要是兩點之間是一條無向邊，則改成兩條方向相反的有向邊。

每一條邊的容量是定值；至於流量與剩餘容量，則有三種不同的記錄方式。第一種方式最直覺。第二種方式中庸。第三種方式最精簡，實作簡單，不過最後要計算最大流的時候會比較麻煩。

第一種記錄方式。先前提到，兩條方向相反的有向邊，可以只讓一條邊擁有水流，另一條邊則沒有水流。在此利用沒有水流的那條邊：兩點之間其中一個方向是正流量，是真正流動的方向；另一個方向則是虛設的負流量，用來增加剩餘容量以利溯洄沖減。

一開始還沒有水流的時候：
flow(i, j) = 0;
flow(j, i) = 0;

有一條涓流經過邊ij之後：
flow(i, j) += 流量;
flow(j, i) -= 流量;

有一條涓流經過邊ij，又有一條涓流溯洄沖減，經過邊ji之後：
flow(i, j) = flow(i, j) + 流量1 - 流量2;
flow(j, i) = flow(j, i) - 流量1 + 流量2;

最後可歸納得出，當一條涓流經過邊ij的時候：
flow(i, j) += 流量;
flow(j, i) = -flow(i, j);

真正的流量則是正流量：
true_flow(i, j) = max(flow(i, j), 0);
true_flow(j, i) = max(flow(j, i), 0);

剩餘容量以管線的容量上限和流量相減而得：
residue(i, j) = capacity(i, j) – flow(i, j);
residue(j, i) = capacity(j, i) – flow(j, i);

typedef int Graph[10][10]; // adjacency matrix Graph C, F, R; // 容量上限、流量、剩餘容量 void one_stream_pass_ij() { memcpy(R, C, sizeof(C)); // 最初每一條邊的剩餘容量等於容量上限 memset(F, 0, sizeof(F)); // 最初的流量為零 F[i][j] = F[i][j] + 流量; F[j][i] = -F[i][j]; R[i][j] = C[i][j] - F[i][j]; R[j][i] = C[j][i] - F[j][i]; }

第二種記錄方式。只要有涓流經過了管線，就把涓流流量直接累加在管線流量。雖然這種記錄方式會讓流量違背容量限制，可是在剩餘容量正確的情況下，還是能找出最大流。

令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。

一開始還沒有水流的時候：
flow(i, j) = 0;
flow(j, i) = 0;

有一條涓流經過邊ij之後：
flow(i, j) += 流量;
flow(j, i) 保持不變;

有一條涓流經過邊ij，又有一條涓流溯洄沖減，經過邊ji之後：
flow(i, j) += 流量1;
flow(j, i) += 流量2;

最後可歸納得出，當一條涓流經過邊ij的時候：
flow(i, j) += 流量;
flow(j, i) 保持不變;

真正的流量是把雙向流量等量減少後而得（去掉溯洄沖減的部分）：
true_flow(i, j) = flow(i, j) - min(flow(i, j), flow(j, i));
true_flow(j, i) = flow(j, i) - min(flow(i, j), flow(j, i));

剩餘容量以管線的容量上限和雙向流量計算而得：
residue(i, j) = capacity(i, j) – (flow(i, j) - flow(j, i));
residue(j, i) = capacity(j, i) – (flow(j, i) - flow(i, j));

typedef int Graph[10][10]; // adjacency matrix Graph C, F, R; // 容量上限、流量、剩餘容量 void one_stream_pass_ij() { memcpy(R, C, sizeof(C)); // 最初每一條邊的剩餘容量等於容量上限 memset(F, 0, sizeof(F)); // 最初的流量為零 F[i][j] = F[i][j] + 流量; R[i][j] = C[i][j] - F[i][j] + F[j][i]; R[j][i] = C[j][i] - F[j][i] + F[i][j]; }

第三種記錄方式。是第一種記錄方式的相反面向，主角改為剩餘容量，只要有涓流經過了管線，正方向剩餘容量會減少，反方向剩餘容量會增加。

令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。

一開始還沒有水流的時候：
residue(i, j) = capacity(i, j);
residue(j, i) = capacity(j, i);

有一條涓流經過邊ij之後：
residue(i, j) -= 流量;
residue(j, i) += 流量;

有一條涓流經過邊ij，又有一條涓流溯洄沖減，經過邊ji之後：
residue(i, j) = residue(i, j) - 流量1 + 流量2;
residue(j, i) = residue(j, i) + 流量1 - 流量2;

最後可歸納得出，當一條涓流經過邊ij的時候：
residue(i, j) -= 流量;
residue(j, i) += 流量;

真正的流量以管線的容量上限和剩餘流量相減而得，而且是正流量：
true_flow(i, j) = max(capacity(i, j) – residue(i, j), 0);
true_flow(j, i) = max(capacity(j, i) – residue(j, i), 0);

typedef int Graph[10][10]; // adjacency matrix Graph C, F, R; // 容量上限、流量、剩餘容量 void one_stream_pass_ij() { memset(F, 0, sizeof(F)); // 最初的流量為零 memcpy(R, C, sizeof(C)); // 最初每一條邊的剩餘容量等於容量上限 R[i][j] -= 流量; R[j][i] += 流量; F[i][j] = max(C[i][j] - R[i][j], 0); F[j][i] = max(C[j][i] - R[j][i], 0); }

找出一個最大流＋計算最大流的流量

typedef int Graph[10][10]; // adjacency matrix Graph C, F, R; // 容量上限、流量、剩餘容量 int Ford_Fulkerson(int s, int t) // 源點、匯點 { memset(F, 0, sizeof(F)); // 最初的流量為零 while (存在一條擴充路徑：C[i][j] - F[i][j] > 0) for (這條擴充路徑的每一條邊ij) { F[i][j] += 擴充路徑流量; F[j][i] = -F[i][j]; } } void Ford_Fulkerson(int s, int t) { memset(F, 0, sizeof(F)); // 最初的流量為零 while (存在一條擴充路徑：C[i][j] - F[i][j] + F[j][i] > 0) for (這條擴充路徑的每一條邊ij) F[i][j] += 擴充路徑流量; } void Ford_Fulkerson(int s, int t) { memcpy(R, C, sizeof(C)); // 最初每一條邊的剩餘容量等於容量上限 while (存在一條擴充路徑：R[i][j] > 0) for (這條擴充路徑的每一條邊ij) { R[i][j] -= 擴充路徑流量; R[j][i] += 擴充路徑流量; } }

演算法

Augmenting Path Algorithm改良版。擴充路徑是源點到匯點的最短路徑（管線長度皆為1），並且擴充流量至瓶頸。這種方式可以避免浪費管線空間，避免反覆地溯洄沖減，更快找到最大流。

不斷找最短擴充路徑，直到找不到為止，即得最大流。
最多找VE次就能達到最大流。

達到最大流，需要的最短擴充路徑數量。
（Edge Labeling with Shortest Distance）

剩餘網路的每一條邊，皆標記一個距離數值，數值大小是源點到該邊的最短距離。

以最短路徑擴充流量至瓶頸，某些邊的距離數值會增加，沒有任何一條邊的距離數值會減少。宏觀來看，距離數值與日俱增。

擴充路徑是最短路徑。瓶頸之處，新增的反向邊，比起原先的正向邊，距離數值至少多一。從彼端繞過來一定比較遠。

瓶頸正向邊：距離數值增加，變成無限大。（水滿了，從剩餘網路之中消失。）
瓶頸反向邊：距離數值不變，比正向邊至少多一。（原先就有反向邊。）
　　　　　　距離數值增加，比正向邊至少多一。（原先沒有反向邊，新增反向邊。）
　其餘的邊：距離數值不變。（瓶頸斷掉，但是有替代路線。或者尚未遭遇瓶頸。）
　　　　　　距離數值增加。（瓶頸斷掉，繞遠路。）

甲、最差情況下，每次擴充流量，整體距離數值只增加1。乙、圖上總共E條邊，每條邊的距離數值範圍為0到V-1。因此至多VE條最短擴充路徑，就能達到最大流。

達到最大流，需要的最短擴充路徑數量。
（Vertex Labeling with Shortest Distance）

剩餘網路的每一個點，皆標記一個距離數值，數值大小是源點到該點的最短距離。

每次以最短路徑擴充流量至瓶頸之後，最短路徑上的點的距離數值不見得會增加；源點到該點的所有最短路徑們通通截斷之後，距離數值才會增加。因此這種方式估計不出結果！

時間複雜度

以BFS尋找O(VE)條擴充路徑的時間。

圖的資料結構使用Adjacency Matrix，便是O(V³E)；圖的資料結構使用Adjacency Lists，便是O((V+E)VE)，通常簡單寫成O(VE²)。

找出一個最大流＋計算最大流的流量

typedef int Graph[10][10]; // adjacency matrix Graph C, F, R; // 容量上限、流量、剩餘容量 bool visit[10]; // BFS經過的點 int path[10]; // BFS tree int flow[10]; // 源點到各點的流量瓶頸 int BFS(int s, int t) // 源點與匯點 { memset(visit, false, sizeof(visit)); queue<int> Q; // BFS queue visit[s] = true; path[s] = s; flow[s] = 1e9; Q.push(s); while (!Q.empty()) { int i = Q.front(); Q.pop(); for (int j=0; j<10; ++j) // 剩餘網路找擴充路徑 if (!visit[j] && R[i][j] > 0) { visit[j] = true; path[j] = i; // 一邊找最短路徑，一邊計算流量瓶頸。 flow[j] = min(flow[i], R[i][j]); Q.push(j); if (j == t) return flow[t]; } } return 0; // 找不到擴充路徑了，流量為零。 } int Edmonds_Karp(int s, int t) { memset(F, 0, sizeof(F)); memcpy(R, C, sizeof(C)); int f, df; // 最大流的流量、擴充路徑的流量 for (f=0; df=BFS(s, t); f+=df) // 更新擴充路徑上每一條邊的流量 for (int i=path[t], j=t; i!=j; i=path[j=i]) { F[i][j] = F[i][j] + df; F[j][i] = -F[i][j]; R[i][j] = C[i][j] - F[i][j]; R[j][i] = C[j][i] - F[j][i]; } return f; }

計算最大流的流量

int adj[10][10]; // adjacency matrix int q[10], *qf, *qb; // BFS queue int p[10]; // BFS tree int Edmonds_Karp(int s, int t) { int f = 0; // 最大流的流量 while (true) // 不斷找擴充路徑直到找不到為止 { // BFS找擴充路徑 memset(p, -1, sizeof(p)); qf = qb = q; p[*qb++ = s] = s; while (qf < qb && p[t] == -1) for (int i = *qf++, j = 0; j < 10; ++j) if (p[j] == -1 && adj[i][j]) p[*qb++ = j] = i; if (p[t] == -1) break; // 更新擴充路徑上每一條邊的流量 int df = 1e9; for (int i = p[t], j = t; i != j; i = p[j = i]) df = min(df, adj[i][j]); for (int i = p[t], j = t; i != j; i = p[j = i]) adj[i][j] -= df, adj[j][i] += df; f += df; } return f; }

UVa 820 10330 10779 563 10511 10983

演算法

Shortest Augmenting Path Algorithm改良版。一口氣找到一樣長的最短擴充路徑們。

重覆以下動作最多V-1次，直到無法擴充流量：
1. 計算residual network各點到源點（匯點）的最短距離。
2. 建立admissible network。
3. 尋找blocking flow，並擴充流量。

Admissible Network

剩餘網路上面，以源點（匯點）作為起點，計算源點（匯點）到每一點的最短距離。

剩餘網路上面，一條由源點往匯點方向的邊、兩端點最短距離相差一，稱作「容許邊Admissible Edge」。所有容許邊，整體視作一張圖，稱作「容許網路Admissible Network」。

容許網路是有向無環圖（DAG）、分層圖（Level Graph）。容許網路可以畫成一層一層的模樣，只有相鄰的層有邊。

容許網路就是剩餘網路的「最短路徑圖」。

容許網路上面，任意一條由源點到匯點的路徑，都是最短擴充路徑。藉由容許網路，可以迅速找到一樣長的最短擴充路徑們。

Blocking Flow

容許網路上面，一個源點到匯點的流，無法再擴充流量，稱作「阻塞流」，通常有許多種，也不必是最大流。

容許網路上面，逐次找到一樣長的最短擴充路徑們，並且每次都讓擴充的流量到達瓶頸，直到找不到為止；整體形成阻塞流。

演算法：找出一個阻塞流

容許網路上面，尋找最短擴充路徑，不必溯洄沖減。溯洄沖減會增加路徑長度，最後得到的不是最短擴充路徑。

由源點隨意往匯點走，若遇到死胡同，就重頭開始走，下次避免再走到死胡同。若順利走到匯點，就形成一條最短擴充路徑，並且擴充流量。

改由匯點隨意往源點走，就不會遇到死胡同。

一條最短擴充路徑，至少有一條邊是瓶頸。容許網路最多只有E條邊能作為瓶頸，所以一個阻塞流最多只有E條最短擴充路徑。

從源點走到匯點並擴充流量需時O(V)，最多有O(E)條最短擴充路徑，所以找出一個阻塞流的時間複雜度是O(VE)。

另外，使用「Link-Cut Tree」記錄容許網路，時間複雜度可以加速到O(ElogV)。

達到最大流，需要的阻塞流數量。
（Vertex Labeling with Shortest Distance）

前面章節利用Vertex Labeling with Shortest Distance估計不出結果，這裡卻可以。

剩餘網路上面，以阻塞流擴充流量，就斷絕了所有一樣長的最短擴充路徑。

容許網路上面，所有由源點到匯點的最短路徑們都阻塞了。剩餘網路上面，源點到匯點的最短距離會增加，下次的最短擴充路徑會更長；擴充流量而新增的反向邊，也不會減少源點到匯點的距離。

擴充路徑的長度範圍是1到V-1（長度為0表示源點與匯點重疊）。因此最多找V-1次阻塞流，就一定沒有擴充路徑了。

時間複雜度

找一個阻塞流需時O(VE)，最多找O(V)次，總時間複雜度O(V²E)。

找出一個最大流＋計算最大流的流量

const int V = 100, E = 1000; int adj[V]; // adjacency lists，初始化為-1。 struct Element {int b, r, next;} e[E*2]; int en = 0; void addedge(int a, int b, int c) { e[en] = (Element){b, c, adj[a]}; adj[a] = en++; e[en] = (Element){a, 0, adj[b]}; adj[b] = en++; } int d[V]; // 最短距離 bool visit[V]; // BFS/DFS visit record int q[V]; // queue // 計算最短路徑，求出容許網路。 int BFS(int s, int t) { memset(d, 0x7f, sizeof(d)); memset(visit, false, sizeof(visit)); int qn = 0; d[s] = 0; visit[s] = true; q[qn++] = s; for (int qf=0; qf<qn; ++qf) { int a = q[qf]; for (int i = adj[a]; i != -1; i = e[i].next) { int b = e[i].b; if (e[i].r > 0 && !visit[b]) { d[b] = d[a] + 1; visit[b] = true; q[qn++] = b; if (b == t) return d[t]; } } } return V; } // 求出一條最短擴充路徑，並擴充流量。 int DFS(int a, int df, int s, int t) { if (a == t) return df; if (visit[a]) return 0; visit[a] = true; for (int i = adj[a]; i != -1; i = e[i].next) { int b = e[i].b; if (e[i].r > 0 && d[a] + 1 == d[b]) { int f = DFS(b, min(df, e[i].r), s, t); if (f) { e[i].r -= f; e[i^1].r += f; return f; } } } return 0; } int dinic(int s, int t) { int flow = 0; while (BFS(s, t) < V) while (true) { memset(visit, false, sizeof(visit)); int f = DFS(s, 1e9, s, t); if (!f) break; flow += f; } return flow; }

UVa 10546

延伸閱讀：Malhotra-Kumar-Maheshwari Algorithm

http://www.cs.cornell.edu/Courses/cs4820/2013sp/handouts/DinicMPM.pdf

容許網路上面，定義一個節點的容量是min(所有出邊總和, 所有入邊總和)，容量最小的節點即是瓶頸。

尋找阻塞流，不斷找到擴充路徑經過瓶頸（切兩段，先往源點找、再往匯點找），使用Binary Heap找瓶頸為O(V²logV)；使用Fibonacci Heap找瓶頸為O(V²)。找V次阻塞流為O(V³)。

演算法

容量視作二進位數字，從最高數量級開始，每回合添加一個位數，並且擴充流量。

重複以下步驟logC回合：
1. 每條邊容量翻倍：流量隨著翻倍。
2. 每條邊容量加零或加一。
3. 尋找擴充路徑（或擴充流），填滿多出的容量，達到最大流。

時間複雜度

甲、總共logC回合。C是最大的管線容量。

乙、每回合開始之前，源點到匯點的剩餘容量已經填滿。每回合當中，添加到圖上各條邊的容量只有0或1，剩餘容量頂多增加E，流量頂多擴充E。換句話說，每回合至多E條擴充路徑，就能達到最大流。

丙、找一條擴充路徑，等同一次Graph Traversal的時間。

圖的資料結構使用Adjacency Matrix，便是O(V²ElogC)；圖的資料結構使用Adjacency Lists，便是O((V+E)ElogC)，通常簡單寫成O(E²logC)。

計算最大流的流量

typedef int Graph[10][10]; // adjacency matrix Graph C, F, Cp; // 容量上限、流量、逐步增加精度的容量上限 int capacity_scaling(int s, int t) { memset(F, 0, sizeof(F)); memset(Cp, 0, sizeof(Cp)); int f = 0; // 總流量 // int有32個bit。 // 最高位的第32bit用以區分正負值，第31bit才是正整數的最高位。 // 第1bit向左位移30位到第31bit，就是正整數的最高位。 for (int b=1<<30; b; b>>=1) { for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) { // 容量添加一個位數 Cp[i][j] <<= 1; Cp[i][j] += !!(C[i][j] & b); // 流量隨著翻倍 F[i][j] <<= 1; } f <<= 1; f += Ford_Fulkerson(s, t, F, Cp); // 計算最大流 } return f; } typedef int Graph[10][10]; // adjacency matrix Graph C, R; // 容量上限、剩餘容量 void capacity_scaling(int s, int t) { memcpy(R, 0, sizeof(R)); for (int b=1<<30; b; b>>=1) { for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) (R[i][j] <<= 1) += !!(C[i][j] & b); Ford_Fulkerson(s, t, R); // 計算最大流，調整剩餘網路。 } }

壹、push

想像一下：於源點放入足夠水量，然後用力推擠源點，就像針筒注射、發射水槍一樣，讓源點的水一股作氣鑽過整個流網路，最後從匯點噴出水流。

受限於流網路的管線容量瓶頸，水流流量是有上限的。水鑽過流網路的路線，就是一個最大流。匯點噴出的水流流量，就是最大流的流量。

然而電腦程式無法直接實現「一股作氣鑽過整個流網路」，電腦程式只能一個一個算、一步一步算，所以我們只好一個一個點慢慢推進：首先推進源點的水到其它中繼點，再繼續推進中繼點的水到其他中繼點，一個接著一個點慢慢地推進到匯點。

貳、excess和overflowing

為了實現「一個接著一個點慢慢地推進」的想法，便定義圖上每個點都可以儲存水，成了「含水點」，其儲存水量稱作「含水量」。水被推到點上，得以暫時儲存在點上，以後隨時可以繼續推進。

建立含水點、含水量的系統之後，推進順序也無所謂了，因為水一直存在、不會消失，就算推歪方向，也可以往回推，回復原始狀態。

以「含水點」、「含水量」，設計一套找出最大流的方法：
子、先將源點的含水量設定成無限大。
丑、推進源點的水到圖上其他點，慢慢推向匯點，推進順序可隨意。
寅、多餘的水量，會受限於管線容量瓶頸，而留在源點和中繼點上。
卯、最後能夠推進到匯點的水量，就是最大流的流量。

參、residual capacity

推進的同時也記錄管線流量，便可以知道水流流動的情形。管線流量與剩餘容量的概念請參考前面的Augmenting Path Algorithm章節。

推進一個點的水，甲、要注意點的含水量，乙、注意管線的剩餘容量，丙、盡量填滿管線，營造出針筒注射、發射水槍的效果。

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int e[10]; // 各個點的含水量 void push(int i, int j) // 推進i點的水到j點 { // 點上要有足夠水量，且流量不得超過剩餘容量。 int f = min(e[i], C[i][j] - F[i][j]); e[i] -= f; e[j] += f; F[i][j] += f; F[j][i] -= f; }

肆、admissible edge

「一個接著一個點慢慢地推進到匯點」，要確保各點的水是確實地推向匯點、聚集在匯點，避免漫無目的來回推進，避免環狀推進、不斷繞圈圈。因此導入了「水往低處流」的想法。

以「水往低處流」來設計方法、解決問題：
子、推向匯點：源點高、匯點低、其他點排好適當的高低順序。
丑、由源點漫溢：源點是最高點。
寅、朝匯點聚集：匯點是最低點。
卯、避免繞圈圈：不能推水到一樣高的點。只能推水到更低的鄰點。

伍、height label

為了實現「水往低處流」的想法，便定義圖上每個點都有一個「高度值」，並排好高低順序，由高往低推進、由源點向匯點推進。

高低順序有兩種安排方式：甲、反轉所有邊之後，以匯點為起點的最短路徑長度，作為高度值。乙、以源點為起點的最短路徑長度，取負值（可再加常數變成正值），作為高度值。

採用甲有個好處，因為推進規則可以改成：推進一個點的水，只能到、也只需要到「比此點剛好低一層」的鄰點。如此可以讓推進規則變得單純、容易實作，也依舊保持著水往低處流的原則。

排好高低次序，以及改變推進規則後，會出現新麻煩：甲、匯點不是最低點。乙、源點的水可能會推不出去。丙、現在要是推歪方向，就不能往回推了。丁、朝向匯點的管線容量不足時，一個點將會水洩不通。必須尋找其他管線，才能流向匯點。

以下將一一解決這些問題。

陸、source and target

無論是哪一種高低順序安排方式，都不能保證源點最高、匯點最低。採用甲，可以把源點的高度另設為V-1，源點就一定比圖上其他點高；匯點的高度維持為零，匯點就一定比圖上其他點低。V是圖上的點數。

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int d[10]; // 高度 void set_height() { shortest_path(); d[s] = V-1; } // Dijkstra's Algorithm void shortest_path() { bool v[10]; memset(d, 1, sizeof(d)); memset(v, 0, sizeof(v)); d[t] = 0; for (int k=0; k<10; ++k) { int j, min = 1e9; for (int i=0; i<10; ++i) if (!v[i] && d[i] < min) min = d[j = i]; v[j] = true; for (int i=0; i<10; ++i) if (!v[i] && C[i][j]) d[i] = min(d[i], d[j] + 1); } }

柒、preflow

源點的高度設為V-1，推進又只能到「比此點剛好低一層」的鄰點，這造成一開始的時候，可能無法推進源點的水到所有鄰點，或說源點的水可能無法流到所有鄰點。

為了解決這種狀況，一開始的時候，就預先推進源點的水到所有鄰點，稱作「預流」。

int e[10]; // 含水點的含水量 void preflow(int s, int t) { for (int j=0; j<10; ++j) if (C[s][j] && j != s) { e[j] = C[s][j]; F[s][j] = e[j]; F[j][s] = -e[j]; } }

捌、relabel

另外又追加了「抬高」的想法：當一個含水點水洩不通，就稍微抬高它，讓水可以流過其他管線，到達其他鄰點；甚至可以抬高到往回流，矯正水流流向。

現在不必預先設定每個點的高低次序了，只需固定源點和匯點的高度，讓各個點抬高後總是比源點低、比匯點高即可。想要推動一個含水點的水，就抬高此點；抬高一個含水點，就可以推動此點的水。

以「水往低處流」和「抬高含水點」來設計方法、解決問題：
子、推向匯點：抬高一個點到比匯點還高，但不能抬高匯點。
丑、由源點漫溢：源點是最高點，高度設為V-1，並預流。
寅、朝匯點聚集：匯點是最低點，高度設為0。
卯、避免繞圈圈：不能推水到一樣高的點。只能推水到剛好低一層的鄰點。
辰、避免水洩不通：抬高一個點比鄰近的點還高，以紓解積水。
巳、矯正流向：抬高一個點比來源的點還高，以豆退嚕。

玖、saturating push

如果一個含水點有許多鄰點，就先抬高含水點稍高於最低的鄰點，並推水到最低的鄰點，並盡量令管線滿溢；如果還有剩水，就再抬高含水點稍高於次低的鄰點，並推水到次高的鄰點，依此類推。以匯點的角度來看，朝向匯點的各條管線會陸陸續續流過水流並且滿溢，最後就會得到最大流。各位可以觀察看看。

當一個含水點水洩不通，表示下游已經遭遇瓶頸、或說下游管線已經滿溢（甚至根本沒有管線）、或說沒有剩餘容量、或說無法再推更多水到匯點、或說有多餘的水流不到匯點。

當一個含水點水洩不通，就抬高含水點，讓水往回流，矯正流向，替多餘的水，尋求其他出路，流到匯點。相反的，當一個含水點河涸海乾時，就沒有必要抬高此點，找自己麻煩。

void relabel(int i) // 抬高i點，直到能夠推水。 { int mind = 1e9; for (int j=0; j<10; ++j) if (C[i][j] - F[i][j] > 0) mind = min(mind, d[j]); d[i] = mind + 1; }

拾、retreat（沒有專用術語，故自行命名）

當水量過剩，又不斷抬高圖上每個點，最後圖上每個點都會比源點還高，所有剩水都會回歸源點。這剛好可以作為演算法的閉幕。此時圖上的水流流動情形就是最大流。

以「水往低處流」和「抬高含水點」來設計方法、解決問題：
子、推向匯點：抬高一個點到比匯點還高，但不能抬高匯點。
丑、回歸源點：抬高一個點到比源點還高，但不能抬高源點。
寅、由源點漫溢：源點是最高點，高度設為V-1。
卯、朝匯點聚集：匯點是最低點，高度設為0。
辰、避免繞圈圈：不能推水到一樣高的點。只能推水到剛好低一層的鄰點。
巳、避免水洩不通：抬高一個點比鄰近的點還高，以紓解積水。
午、矯正流向：抬高一個點比來源的點還高，以豆退嚕。

小結

欲讓水「一股作氣鑽過整個流網路」計算最大流，電腦卻只能「逐點推進」，只好製作一些中繼的「含水點」，加入「水往低處流」的概念，以匯點為起點的最短路徑長度設定「高低次序」，迫使水流向匯點。但是卻導致「源點不是最高點」、「源點無法推水」、「無法矯正流向」、「水洩不通」等諸多問題。於是又出現了「設定源點匯點高度」、「預流」、「抬高」的想法，解決了上述問題，從此亦不再需要安排「高低次序」。至於無法推到匯點的剩水，恰可藉由「抬高」而回歸源點，演算法完美結束。

接下來開始詳細列出演算法內容。

Preflow

推動源點的水到所有鄰點。
（源點可以不必設定水量，不影響結果。)

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int e[10]; // 含水點的含水量 void preflow(int s) { for (int j=0; j<10; ++j) if (C[s][j] && j != s) { e[j] = C[s][j]; F[s][j] = e[j]; F[j][s] = -e[j]; } } int adj[10][10]; // adjacency matrix int e[10]; // 含水點的含水量 void preflow(int s) { for (int j=0; j<10; ++j) if (C[s][j] && j != s) { adj[j][s] += (e[j] = adj[s][j]); adj[s][j] = 0; } }

Push

給定一個含水點和一個與其相鄰的點，推水過去。
以下是允許進行Push的條件，確定符合後才得進行Push：
壹、含水點不是源點和匯點。（源點已預流，匯點收集水。）
貳、含水點仍有水。
參、含水點到其鄰點的邊仍有剩餘容量。
肆、鄰點是比含水點低一層的點。

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int e[10]; // 高度、含水點的含水量 void push(int i, int j) { // 水量要足，且不得超過剩餘容量。 int f = min(e[i], C[i][j] - F[i][j]); e[i] -= f; e[j] += f; F[i][j] += f; F[j][i] -= f; } int adj[10][10]; // adjacency matrix int e[10]; // 高度、含水點的含水量 void push(int i, int j) { // 水量要足，且不得超過剩餘容量。 int f = min(e[i], adj[i][j]); e[i] -= f; e[j] += f; adj[i][j] -= f; adj[j][i] += f; }

Relabel

給定一個含水點，抬高此含水點。
以下是允許進行Relabel的條件，確定符合後才得進行Relabel：
壹、含水點不是源點和匯點。（請參考Push，沒必要推動就沒必要抬高。）
貳、含水點仍有水。
參、含水點水洩不通。
　　含水點藉由有剩餘容量的邊，所連到的鄰點，這些鄰點的高度都小於等於含水點。
　　（當含水點仍找得到低一層的鄰點可以推水過去，就不能抬高。）

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int d[10]; // 高度 void relabel(int i) { int mind = 1e9; for (int j=0; j<10; ++j) if (C[i][j] - F[i][j] > 0) mind = min(mind, d[j]); d[i] = mind + 1; } int adj[10][10]; // adjacency matrix int d[10]; // 高度 void relabel(int i) { for (int j=0; j<10; ++j) if (adj[i][j]) d[i] = min(d[i], d[j]); d[i]++; }

演算法

1. 把圖上每個點的高度設為零。
   （或者是以匯點作為起點的最短路徑長度作為高度，不影響結果。）
2. 設定起點的高度是V-1（以上），V為圖上點數。
3. preflow。
4. 圖上各點不斷push或relabel，次序隨意，直到無法進行為止。
   （或者說，直到圖上除源點匯點以外的所有點都沒水為止。）
5. 匯點所收集的水量，即是最大流的流量。
   多餘的水流回源點後，源點所流出的水量，即是最大流的流量。
   圖上每條邊的水流，總合起來就是最大流。

經由複雜的推導，總算歸納出單純的演算法──僅以三種「點對鄰點之間」的動作preflow、push、relabel，即可求得最大流。十分精采！

時間複雜度

我們針對preflow、push、relabel的次數下手。

preflow：總共一次，O(V)。

relabel：設定匯點的高度為0，源點的高度為V-1。最差情況下，除源點匯點，最高的點升到了2V-3、最低的點升到了V，流不到匯點的水都回歸匯點了，如下圖所示。利用等差級數梯形公式，得知relabel總共最多O(V²)次。

圖的資料結構為Adjacency Matrix，一次relabel需時O(V)，全部的relabel需時O(V³)；圖的資料結構為Adjacency Lists，圖上各點各做一次relabel需時O(E)，全部的relabel需時O(VE)。

saturating push：對一條邊而言，兩個端點高度逐漸升高，高度範圍為0到2V-3，高度相差一時才能推動，一種高度頂多推動一次，所以一條邊的saturating push總共最多O(V)次。

圖的資料結構為adjacency lists，一次push需時O(1)，一條邊的saturating push總共最多O(V)次，圖上總共E條邊，全部的saturating push需時O(VE)。

non-saturating push：同上，一種高度最多推動V次。由於其端點的V個鄰點升高時會補水給端點、其端點最多補水V次。全部的non-saturating push需時O(V²E)。

歸納上述四項，總時間複雜度O(V²E)，受限於non-saturating push的次數。

計算最大流的流量

實作時我們建立一個queue來儲存含水點。

int adj[10][10]; // adjacency matrix int d[10], e[10]; // 高度、含水點的含水量 int q[150], *qf, *qb; // 存放圖上所有除源點和匯點外的含水點 void preflow(int s) { for (int j=0; j<10; ++j) if (adj[s][j] && j != s) { adj[j][s] += (e[j] = adj[s][j]); adj[s][j] = 0; if (j != s && j != t) *qb++ = j; } } void push(int i, int j) { // 水量要足，且不得超過剩餘容量。 int f = min(e[i], adj[i][j]); e[i] -= f; e[j] += f; adj[i][j] -= f; adj[j][i] += f; } void relabel(int i) { for (int j=0; j<10; ++j) if (adj[i][j]) d[i] = min(d[i], d[j]); d[i]++; } int preflow_push_relabel(int s, int t) { memset(d, 0, sizeof(d)); memset(e, 0, sizeof(e)); qf = qb = q; d[s] = 10 - 1; // 設定源點高度，避免水太早灌回源點。 preflow(s); while (qf < qb) // 除源點匯點外還有含水點就繼續 { int i = *qf++; relabel(i); // 不一定能成功抬高此點，但無妨。 for (int j=0; j<10; ++j) if (d[i] == d[j] + 1 && adj[i][j]) { if (!e[j] && j!=s && j!=t) *qb++ = j; push(i, j); if (!e[i]) break; } if (e[i]) *qb++ = i; } return e[t]; }

想法

順著高低順序推水是我們的初衷。累積足夠水量後，就慢慢往前推動，不要每次都一口氣推水到最低處，便可以減少push的次數。

Discharge

給定一個含水點，不斷使用Push和Relabel把水排掉，直到沒水。
以下是允許進行Discharge的條件，確定符合後才得進行Discharge：
壹、含水點不是源點和匯點。
貳、含水點仍有水。

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int d[10], e[10]; // 高度、含水點的含水量 void discharge(int i) { while (e[i]) // 還有水就繼續排水 { for (int j=0; j<10; ++j) if (d[i] == d[j] + 1 && C[i][j] - F[i][j]) { push(i, j); if (!e[i]) return; // 沒有水就結束 } relabel(i); // 肯定可以抬高 } }

演算法

1. preflow。
2. 不斷找符合條件的含水點實施discharge，
   直到所有含水點（除源點匯點）都沒水為止。

   條件：其他含水點（除源點匯點）的水，
   無法沿著目前的容許網路流入此含水點。

【待確認】

時間複雜度

我們針對preflow、push、relabel的次數下手。preflow、relabel、saturating push的時間複雜度都與先前章節相同。此處只分析non-saturating push的時間複雜度。

【待補文字】

由均攤分析可知non-saturating push總共O(V³)次。總時間複雜度O(V³)。

演算法：一直找最高的含水點discharge
（Highest-Label Preflow-Push Algorithm）

1. preflow。
2. 一直找最高的含水點進行discharge（不包括源點匯點），
   直到圖上無含水點（不包括源點匯點），

演算法：含水點discharge後，若有升高則挪動順序至首
（Relabel-to-front Algorithm）

1. 建立一個list，裡面包含所有點（但不包括源點匯點）。
   註：此list從頭到尾一直都是當下容許網路的拓撲排序。
2. preflow。
3. 按照list順序讀取各點
   甲、如果不是含水點，就繼續下一個點，
   乙、如果是含水點，就discharge，並且於discharge完之後
      a. 如果剛才的discharge有抬高此點（有relabel），
         就把此點移到list開頭，並重新由list開頭讀取。
      b. 如果剛才的discharge沒有抬高此點（沒有relabel），
         就繼續下一個點。

演算法：含水點以FIFO順序discharge
（FIFO Preflow-Push Algorithm）

1. 建立一個queue，裡面只放含水點（但不包括源點匯點），含水點不會重複。
2. preflow，順便把含水點都塞入queue。
3. queue不斷彈出點，進行discharge，直到queue無點。
   若discharge時產生了queue裡面沒有的含水點，就塞入queue。

註記

此演算法沒有廣為人知的正式名稱。

此演算法為Ahuja與Orlin於1991年發表，論文名稱是Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems。該篇論文中同時發表了兩個最大流演算法，因此若直接稱呼Distance-directed Augmenting Path Algorithm，會無法準確指出是哪一個演算法。

Ahuja與Orlin後來出版一本網路流的書籍，書上描述此演算法為「Shortest Augmenting Path Algorithm改良版」，但是仍未給予一個適切的名稱。

演算法

Preflow-Push Algorithm的加強版。以DFS的順序沿著容許邊行走，當遇到死胡同，就relabel，並且回溯，尋找其他可以到達匯點的路徑。

與Preflow-Push Algorithm不同的地方，在於此演算法是找到匯點之後，才沿著擴充路徑來擴充流量，而不是逐點推水。

時間複雜度仍是O(V²E)。

const int V = 100; int C[V][V], R[V][V]; int h[V], cnt[V+1]; int p[V], pf[V]; int ISAP(int s, int t) { memcpy(R, C, sizeof(C)); memset(h, 0, sizeof(h)); memset(cnt, 0, sizeof(cnt)); cnt[0] = V; pf[s] = 1e9; p[s] = s; int flow = 0, i = s, j = 0, f = 1e9; while (h[s] < V) { // 尋找一條容許邊 for (j=0; j<V; ++j) if (R[i][j] > 0 && h[i] == h[j] + 1) break; // 沿著容許邊前進，到達匯點，擴充流量。 if (j == t) { f = min(f, R[i][j]); flow += f; for (; j != s; j = i, i = p[i]) { R[i][j] -= f; R[j][i] += f; } // 回到源點，繼續找擴充路徑。 f = 1e9; i = s; } // 沿著容許邊前進 else if (j < V) { pf[j] = f; p[j] = i; f = min(f, R[i][j]); i = j; } // relabel，並且沿著先前的路徑撤退。 else { if (--cnt[h[i]] == 0) h[s] = V; ++cnt[++h[i]]; f = pf[i]; i = p[i]; } } return flow; } const int V = 100; int C[V][V], R[V][V]; int h[V], cnt[V+1]; int DFS(int i, int df, int s, int t) { // 到達匯點，得到擴充流量大小。 if (i == t) return df; // 尋找容許邊 for (int j=0; j<V; ++j) if (R[i][j] > 0 && h[i] == h[j] + 1) { // 沿著容許邊前進 int f = DFS(j, min(df, R[i][j]), s, t); // 到達匯點，擴充流量。 if (f) { R[i][j] -= f; R[j][i] += f; return f; } } // relabel，並且沿著先前的路徑撤退。 if (--cnt[h[i]] == 0) h[s] = V; // 演算法結束 ++cnt[++h[i]]; return 0; } int ISAP(int s, int t) { memcpy(R, C, sizeof(R)); memset(cnt, 0, sizeof(cnt)); // cnt[0] = V; // 匯點永不升高，高度為零的點永遠存在。 // 大可不必關心高度為零的點。 int flow = 0; while (h[s] < V) flow += DFS(s, 1e9, s, t); return flow; }

尋找擴充路徑，沿著容許邊行走，從源點走到匯點，途中各點的高度逐次減一。缺一不可。

任何一種高度出現了、又完全消失之後，表示源點到匯點往後無法貫通，開始retreat，可以直接結束演算法。此即cnt的功用。

UVa 10983

演算法

引入阻塞流的概念。以Backtracking的順序而非DFS的順序沿著容許邊行走，尋找擴充流而非擴充路徑。

特色是尋找每一點到匯點的阻塞流（水足夠時）、也就是尋找局部的阻塞流！每次回溯皆實施relabel，隨時調校局部的最短路徑長度！

時間複雜度O(V²E)。

const int V = 100; int C[V][V], R[V][V]; int h[V], cnt[V+1]; int DFS(int i, int df, int s, int t) { if (i == t) return df; int tf = df; for (int j=0; j<V; ++j) if (R[i][j] > 0 && h[i] == h[j] + 1) { int f = DFS(j, min(df, R[i][j]), s, t); // 不斷尋找其他擴充路徑，直到水量不足。 R[i][j] -= f; R[j][i] += f; df -= f; if (df == 0 || h[S] == V) return tf - df; } // 每次backtrack的時候就relabel！有點類似discharge。 int newh = h[i]; for (int j=0; j<V; ++j) if (R[i][j] > 0) newh = min(newh, h[j]); if (--cnt[h[i]] == 0) h[s] = V; else ++cnt[h[i] = newh + 1]; return tf - df; } int ISAP(int s, int t) { memcpy(R, C, sizeof(R)); memset(cnt, 0, sizeof(cnt)); // cnt[0] = V; int flow = 0; while (h[s] < V) flow += DFS(s, 1e9, s, t); return flow; }

延伸閱讀：height label

有了height label的概念之後，我們可以重新審視之前的擴充路徑演算法，給予更簡潔的解釋。

Augmenting Path Algorithm（Ford-Fulkerson Algorithm）
不使用height label。
隨便找擴充路徑。

Shortest Augmenting Path Algorithm（Edmonds-Karp Algorithm）
每回合都用BFS重新建立height label，
同時用BFS找一條擴充路徑。

Blocking Flow Algorithm（Dinic's Algorithm）
每回合都用BFS重新建立height label，
每回合都用多次DFS找擴充路徑（最後形成阻塞流）。

Improved Shortest Augmenting Path Algorithm
一開始用BFS建立height label（也可以全部設定為零），
每回合都用DFS找擴充路徑。

摘要

最大流問題只有四個要素：
　甲、容量（Flow Network）。甲≥0。
　乙、流量（Flow）。甲≥乙≥0。
　丙、剩餘容量（Residual Network）。甲減乙、反向乙。
　丁、遵行方向（Admissible Network）。丁屬於丙：邊兩端高度差為一。

最大流問題：
　給定甲暨源點匯點，令乙趨近甲，求乙。

最大流演算法：
　以丙的視角看問題，有隙就流。（最大流最小割定理）
　以丁的視角看問題，可以縮短流動路線，加速演算法。

最大流演算法有兩大類：
　一、擴充路徑法（率先流到匯點）
　Augmenting Path Algorithm          丙上隨便找一條擴充路徑，不斷找。
　(Ford-Fulkerson Algorithm)         O(EF)

　Shortest Augmenting Path Algo.     丙上BFS找一條擴充路徑，最多VE次。
　(Edmonds-Karp Algorithm)           O(VEE)

　Blocking Flow Algorithm            丁上找擴充流，最多V次。
　(Dinic's Algorithm)                O(VVE)

　Improved Shortest Augmenting       丁上找擴充路徑，最多VE次。
　Path Algorithm                     O(VVE)

　Capacity Scaling Algorithm         限制甲尺度找擴充流，最多logC次。
　                                   O(EElogC)

　二、預流推進法（率先流離源點）
　Preflow-Push Algorithm             隨性推  O(VVE)
　Relabel-to-front Algorithm         插隊推  O(VVV)
　FIFO Preflow-Push Algorithm        FIFO推  O(VVV)
　Highest-Label Preflow-Push Algo.   最高推  O(VVV)

http://jorlin.scripts.mit.edu/Max_flows_in_O(nm)_time.html

目前時間複雜度最低的演算法。使用一些糟糕的手法硬湊出來的，缺乏實務價值。