Flow Network

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

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

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

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

Flow（Network Flow）

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

Flow中譯為「流」。一個流便是由源點經管線至匯點的水流。一個流的權重（總流量），即是源點灌入的水流流量，同時也是匯點泄出的水流流量。

Maximum Flow（Max-Flow）

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

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

Minimum Flow（Min-Flow）

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

圖例：不屬於流的玩意

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

圖例：合流、分流、交流

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

圖例：產生迴圈的流

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

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

感情很好的兩個點，一般視作內地裡波濤洶湧，流量無限大。

多重的邊變成單獨的邊

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

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

點的權重變成邊的權重

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

因此，在Flow的問題當中，點的權重可以改為邊的權重，最後只需要考慮邊的權重就行了。只考慮邊的權重，事情也簡單多了。

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

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

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

無向邊變成有向邊

無向邊允許挑選流動方向，兩個方向都有相同的容量上限與容量下限，可以改為兩條方向相反的有向邊。但要注意一點是：這兩條方向相反的有向邊，只有其中一條可以用於流動。

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

一條小水流流量的瓶頸

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

附帶一提，由於水流不會滲漏、不會淤滯，所以一條由源點流至匯點的小水流，其流動路徑上任意一條邊的流量，都會等於小水流的水流流量。

水流總流量的瓶頸

水一定從源點流至匯點。現在把圖上的點，依地理位置劃分作兩區，一區鄰近源點，另一區鄰近匯點──由源點區流入到匯點區的水流總流量，一定會小於等於由源點區橫跨到匯點區的管線總容量。反方向亦同。

如此說來，由源點流至匯點的水流總流量，其總流量的瓶頸，會是所有分區方式裡面，由源點區橫跨到匯點區的管線總容量之中，管線總容量最小的一個分區方式。

附帶一提，由於水流不會滲漏、不會淤滯，所以一個從源點流至匯點的流，其任意一種分區方式裡面，由源點區流入到匯點區的總流量，減去由匯點區流回到源點區的總流量，會等於由源點流至匯點的水流總流量。

Max-Flow Min-Cut Theorem

【讀者若不懂Cut，請參考「Graph Theory: Cut」。】

方才的分兩區方式有點籠統，很難定義誰鄰近源點，誰鄰近匯點，因此資訊學家嘗試以Cut來取代方才的說法，希望藉由Cut把事情說得更嚴謹一些。然而這也稍微偏離了原來的瓶頸概念。

水一定從源點流至匯點。現在在圖上取一個源點與匯點不同側的Cut，也就是把圖上的點，劃分作兩側，一側包含源點，一側包含匯點──由源點側流入到匯點側的水流總流量，一定會小於等於由源點側橫跨到匯點側的管線總容量。反方向亦同。

如此說來，由源點流至匯點的水流總流量，其總流量的瓶頸，會是所有的源點與匯點不同側的割裡面，由源點側橫跨到匯點側的管線總容量之中，管線總容量最小的一個割。

附帶一提，由於水流不會滲漏、不會淤滯，所以一個從源點流至匯點的流，其任意一種分區方式裡面，由源點側流入到匯點側的總流量，減去由匯點側流回到源點側的總流量，會等於由源點流至匯點的水流總流量。

最後整理一下：

在一張圖上面任意取一個源點與匯點不同側的割。
定義流過此割的流量：由源點側流入到匯點側的總流量，減去由匯點側流回到源點側的總流量。
定義橫跨此割的容量：由源點側橫跨到匯點側的總容量。

根據瓶頸的概念，流過此割的流量會小於等於橫跨此割的容量。
因此「最大流的流量」等於「管線容量的最小割」。

由於水流不會滲漏、不會淤滯，在一個流當中，任取一個割，流過此割的流量等於水流總流量。

Ford-Fulkerson Algorithm
（Augmenting Path Algorithm）

給定一張有源點和匯點的圖，找出其中一個Max-Flow。

想法

在一個裝水的塑膠袋底部戳個洞，水就會流出來。戳越多洞，水就流出的越多。這意味著水一旦有隙可乘，就一定會源源而來、滔滔而至。要找最大流，其實與這個道理相同，讓水流不停地鑽空隙流至匯點，當無法再找到空隙時，就是極限了，就是最大流了。

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

溯洄沖減

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

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

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

Residual Capacity

水流要遵守管線容量限制。每一條涓流也都要遵守管線容量限制，其流量不得超過容量上限，只得就管線所剩下的空間來流動。residual capacity即是指管線剩下的空間，中譯「剩餘容量」。

一開始所有管線都是空的、沒有流量，管線的剩餘容量即等於管線容量上限：

令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。
flow[i][j] = 0;
flow[j][i] = 0;
residue[i][j] = capacity[i][j];
residue[j][i] = capacity[j][i];

當一條涓流流過管線後，就會變成：

如果有一條涓流流經邊ij。
flow[i][j] += 流量;
residue[i][j] = capacity[i][j] – flow[i][j];
residue[j][i] = capacity[j][i];

另外也要考慮溯洄沖減的涓流：

如果有一條涓流流經邊ij，然後之後又有一條涓流流經邊ji。
flow[i][j] += 流量1;
flow[j][i] += 流量2;
residue[i][j] = capacity[i][j] – (flow[i][j] - flow[j][i]);
residue[j][i] = capacity[j][i] – (flow[j][i] - flow[i][j]);

只要有涓流流過了某條管線，就把涓流的流量累加到該條管線的流量。這種方式可以計算出一條管線的兩個方向各流過了多少流量。

另外還有一套更常用的方式。一條管線的水流其實只會朝其中一個方向流動，另一個方向則是「沒有流量」，但「可供溯洄」。在此可以利用相反數：

如果有一條涓流流經邊ij。
flow[i][j] += 流量;
flow[j][i] = -flow[i][j];

如此一來，剩餘容量則可以直接以同一條管線的容量上限和流量相減而得：

residue[i][j] = capacity[i][j] – flow[i][j];
residue[j][i] = capacity[j][i] – flow[j][i];

這種方式下，一條管線絕對只有一個方向是正流量，另一個方向則是虛設的負流量。

各位可以思考一下剛剛介紹的這些方式，是否能用在有向圖和無向圖。

Augmenting Path

中譯「擴充路徑」。把握目前管線所剩下的空間，以及利用溯洄沖減方式，流出一條由源點至匯點的小小涓流，就是一條augmenting path，就是一條增加總流量的路徑，其流量可多可少（一般來說流量越多越好，能較快達到最大流）。只要一直找到augmenting path，總流量就會逐漸增加。

換個角度想，augmenting path就是在一張剩餘容量的圖上，任意一條由源點到匯點的路徑。只要一直找到augmenting path，剩餘容量就會逐漸減少，總流量就會逐漸增加。

每次流出一條涓流後，涓流中所有的邊，都會開放給之後的涓流進行溯洄沖減──也可以想做是剩餘容量圖上多了很多逆向管線，逆向管線的剩餘容量，等於涓流流過的流量。augmenting path可以經過這些逆向管線，來改善各條涓流的路線，妥善地利用剩餘容量，努力地增加總流量。

augmenting path的概念可以用於許多地方。這裡列出一題相關問題，供各位練習。

UVa 10806

正確性證明：利用水流總流量瓶頸（利用Max-Flow Min-Cut Theorem）

一張圖還找得到augmenting path的話，表示目前不是最大流，因為總流量得以藉由augmenting path而增加。

一張圖找不到augmenting path的話，表示這張圖中間有些管線已經沒有剩餘容量、已經滿溢（或根本沒有管線），造成水流無法由源點區流至匯點區，才會找不到augmenting path。

管線滿溢，等同於遇到了瓶頸，所以目前的流就是一個最大流。由源點開始，尚可流及的點集合（瓶頸之前），和無法流及的點集合（瓶頸之後），就是一個源點與匯點不同側的最小割。

另外值得順便一提的是，在一個最大流中，能找到的最小割不只一種。一般來說，要找最小割，可以先找源點側，也可以先找匯點側（邊的方向要反過來看），不過還是會有其他種類的最小割，這些最小割通常都很難被發現。

UVa 10480

演算法

不斷的找augmenting path，直到找不到為止。所有augmenting path總合起來便是Max-Flow，所有augmenting path的成本總和就是Max-Flow的權重。

augmenting path要怎麼找都可以，不一樣的augmenting path會產生不一樣的Max-Flow。下個章節會說明一種不錯的尋找方式。

時間複雜度

一個最糟糕的情況是：不斷找到流量超級少的augmenting path，時間複雜度是O(E*|f|)，其中E是圖上的邊數，f是最大流的權重。

尋找一個最大流＋計算最大流的權重（adjacency matrix）

typedef int Graph[10][10]; // adjacency matrix Graph C, F. R; // 分別是容量上限、流量、剩餘容量 int Ford_Fulkerson(int s, int t) // 分別是源點、匯點 { memcpy(R, C, sizeof(C)); // 最初每一條邊的剩餘容量等於容量上限 memset(F, 0, sizeof(F)); // 最初的流量為零 int f = 0; // 總流量 while (還有augmenting path) { int df = augmenting path 的流量; for (目前的 augmenting path 中的每一條邊 (i,j) ) { 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; }

Flow Decomposition

一個流有兩種拆解方式，或說是兩種數法：一、以圖上每一條邊的水流來看。二、以一條一條的augmenting path的水流來看。Ford-Fulkerson Algorithm使用後者來數最大流。

Edmond-Karp Algorithm
（Shortest Augmenting Path Algorithm）

給定一張有源點和匯點的圖，找出其中一個Max-Flow。

Edmond-Karp Algorithm是Ford-Fulkerson Algorithm的加強版：每次找擴充路徑的時候，採用BFS，尋找由源點到匯點的最短路徑（想像管線長度皆為1），而且流量越大越好（到達瓶頸容量）。儘量避免浪費管線空間，也避免反覆地溯洄沖消，可以較快找到最大流。

最短路徑作為擴充路徑的好處

一、以點的觀點來看：在剩餘容量圖上，由源點到圖上每個點的最短路徑長度會逐步增加、或保持不變，但絕對不會減少。更進一步來說，每次找到的最短擴充路徑會逐漸變長，呈單調遞增成長。

此處稍做說明。回想Dijkstra's Algorithm所提到的greedy概念：一條最短路徑是由更短的最短路徑所組成。也就是說，由源點到擴充路徑上各個點所形成的路徑們，全部都是最短路徑。

擴充路徑被水流流過後，路徑上有些邊仍會有剩餘容量，仍存在於剩餘容量圖上；有些邊則一點不剩，從剩餘容量圖上消失了。綜合前文所述，這意味著由源點到擴充路徑上某些點的最短路徑已經沒啦。最短的路徑沒有了，所以最短路徑長度必會增加、或不變（當還有另一條一樣長的最短路徑的時候）。

最後再詳加考慮擴充路徑被水流流過之後，剩餘容量圖上增加的逆向邊。多出的這些逆向邊亦不會減少最短路徑的長度。

至此，可以確定以最短路徑作為擴充路徑，其路徑長度與日俱增、不會減少。

二、以邊的觀點來看：在流網路圖上，一條邊成為擴充路徑的瓶頸的次數會低於V/2次。更進一步來說，一張圖上最多只有O(V/2 * E) = O(VE)條擴充路徑。

【待補文字】

時間複雜度

時間複雜度等同於以BFS尋找O(VE)條擴充路徑的時間。圖的資料結構為adjacency matrix的話，便是O((V^2) * VE) = O(V^3 * E)；圖的資料結構為adjacency lists的話，通常把BFS的時間複雜度O(V+E)，省略了V而寫成簡單的O(E)，所以總共是O(E * VE) = O(V^2 * E)。

找出一個最大流＋計算最大流的權重（adjacency matrix）

typedef int Graph[10][10]; // adjacency matrix Graph C, F, R; // 容量上限、流量、剩餘容量 bool visit[10]; // 紀錄BFS經過的點 int path[10]; // 紀錄BFS tree int flow[10]; // 紀錄源點到各個點的流量 // 用法類似於最短路徑演算法的dist陣列 int BFS(int s, int t) // 源點與匯點 { memset(visit, false, sizeof(visit)); queue<int> Q; 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) // 在剩餘容量的圖上找augmenting path 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; // 找不到augmenting path了，流量為零。 } 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; }

下面這個是別人寫的程式碼，相當精簡，可以參考看看：http://shygypsy.com/tools/。

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量（剩餘容量可以相減求得） int q[10], qf, qb; p[10]; // BFS所用的queue int p[10]; // 紀錄BFS tree int Edmonds_Karp(int s, int t) { memset(F, 0, sizeof(F)); int f = 0; // 最大流的流量 while (true) // 不斷找擴充路徑直到找不到為止 { // BFS找augmenting path。 memset(p, -1, sizeof(p)); qf = qb = 0; p[q[qb++] = s] = s; while (qb > qf && p[t] == -1) for (int i=q[qf++], j=0; j<10; ++j) if (p[j] == -1 && F[i][j] - F[j][i] < C[i][j]) p[q[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 <?= C[i][j] - F[i][j] + F[j][i]; for (int i=p[t], j=t; i!=j; i=p[j=i]) F[i][j] += df; f += df; } return f; }

利用找出的最大流，從中找出一個最小割（adjacency matrix）

bool visit[10]; void DFS(int s) { visit[s] = true; for (int t=0; t<10; ++t) if (!visit[t] && F[s][t] < C[s][t]) DFS(t, N); } void find_min_cut(int s, int t) { Edmonds_Karp(s, t); memset(visit, false, sizeof(visit)); DFS(s); for (int i=0; i<10; ++i) // 窮舉源點側的點 if (visit[i]) for (int j=0; j<10; ++j) // 窮舉匯點側的點 if (!visit[j]) if (C[i][j] > 0) // 要確定有邊 cout << "Cut上的邊有" << "由" << i << "到" << j << endl; }

找出一個最大流＋計算最大流的權重（adjacency lists）

// adjacency lists當中的一個節點 struct P { int t, c, f; // 相鄰的點、容量上限、流量 P *next, *op; // 另外加入了一個oppsite，用來快速地指向逆向邊。 inline void set(int _t, int _c, int _f, P* _next, P* _op) { t = _t; c = _c; f = _f; next = _next; op = _op; } }; // 陰險狡詐的開記憶體方法， // 如此就不用一直new和delete。 P m[1000000]; int mN = 0; // Edmonds-Karp會用到的記憶體 P* G[3000+2]; // 流量上限 int q[3000+2], qf, qb; // BFS所用的quque P* p[3000+2]; // 紀錄BFS tree // 建立邊時，必須同時建立兩個方向的邊， // 不然溯洄沖消時會找不到對應的逆向邊。 void add(int a, int b, int c) { P* n1 = &m[mN++], *n2 = &m[mN++]; n1->set(b, c, 0, G[a], n2); n2->set(a, 0, 0, G[b], n1); G[a] = n1; G[b] = n2; } int Edmonds_Karp(int s, int t) { int f = 0; while (true) { memset(p, 0, sizeof(p)); qf = qb = 0; p[q[qb++] = s] = (P*)-1; while (qb > qf && !p[t]) for (P* n=G[q[qf++]]; n; n=n->next) if (!p[n->t] && n->f - n->op->f < n->c) p[q[qb++] = n->t] = n; if (!p[t]) break; int df = 1e9; for (P* n=p[t]; n!=(P*)-1; n=p[n->op->t]) df <?= n->c - n->f + n->op->f; for (P* n=p[t]; n!=(P*)-1; n=p[n->op->t]) n->f += df; f += df; } return f; }

UVa 820 10330 10779 563 10511

Capacity Scaling Algorithm

給定一張有源點和匯點的圖，找出其中一個Max-Flow。

大意是：將容量數值記錄下來，然後設定為零。接著把原本的容量數值，由最高位bit到最低位bit，逐一添加到容量數值的尾端。每添加一個bit就找一次最大流，並持續累計計算的結果。

1. 令 C 為容量上限。C' 為依序添加bit的容量上限，並設為零。
2. 由 C 的最高位bit開始，直到 C 的最低位bit為止，不斷重複下面動作：
	甲、把 C 的該bit添加到 C' 的尾端。
	乙、當前流量成為方才的兩倍。
	丙、填滿新增的容量，以達到最大流：基於當前流量，再找一些擴充路徑。

時間複雜度

一、找一條擴充路徑為一次Graph Traversal的時間，使用adjacency matrix為O(V^2)，使用adjacency lists為O(V+E)。這裡採用adjacency lists的O(V+E)，並省略V變成O(E)。

二、每個步驟中，先前的瓶頸的剩餘容量已經被填滿，而添加到圖上各條邊的容量只有0或1，先前的瓶頸的容量最多只增加1，整張圖來看由源點到匯點的容量最多只增加E。因此，每個步驟最多只會有O(E)條流量為1的擴充路徑，然後就達到當下的最大流了。細節請讀者自行探索。

三、令一張圖的管線容量最大者為C，一一拿出bit，所以這個演算法就會有O(logC)個步驟，以2為底的log。

根據上述三點，整個演算法的時間複雜度是O(E^2 * logC)。當C不大，會比Edmonds-Karp Algorithm快，尤其是Edmonds-Karp Algorithm每次所找到的擴充路徑的流量都很小的時候。

計算最大流的權重（adjacency matrix）

typedef int Graph[10][10]; // adjacency matrix Graph C, F, Cp; // 分別是容量上限、流量、逐步添加bit的容量上限 void capacity_scaling(int s, int t) { memset(F, 0, sizeof(F)); // 最初的流量為零 memset(Cp, 0, sizeof(Cp)); // 設為零，然後逐一添加bit到尾端。 int f = 0; // 總流量 // int有32個bit。 // 最高位的第32bit用以區分正負值，第31bit才是正整數的最高位。 // 第1bit向左位移30位到第31bit，就是正整數的最高位。 for (int b=1<<30; b; b>>=1) { // 圖上每條邊都要添加bit或者是加倍 for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) { // 添加bit到容量上限數值的尾端 (Cp[i][j] <<= 1) += !!(C[i][j] & b); // int d = ( (C[i][j] & b) > 0 ? 1 : 0 ); // tC[i][j] << 1; tC[i][j] += d; // 將目前的流量加倍 F[i][j] <<= 1; } } f <<= 1; f += Ford_Fulkerson(s, t, F, Cp); // 計算當前最大流 } return f; }

Preflow-Push-Relabel Algorithm

給定一張有源點和匯點的圖，找出其中一個Max-Flow。

此演算法會運用到Ford-Fulkerson Algorithm提及的一些概念。讀者在繼續閱讀之前，請先預備知識。

壹、push

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

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

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

貳、excess和overflowing

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

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

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

參、residual capacity

推進的同時也記錄管線流量，便可以知道水流流動的情形。管線流量與剩餘容量的概念請參考前面的Ford-Fulkerson 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

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

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

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

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

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

陸、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] <?= d[j] + 1; } }

柒、preflow

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

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

int e[10]; // 含水點的含水量 void preflow(int s, int t) { for (int j=0; j<N; ++j) if (C[s][j]) { 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 min = 1e9; for (int j=0; j<10; ++j) if (C[i][j] - F[i][j] > 0) min <?= d[j]; d[i] = min + 1; }

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

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

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

小結

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

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

Preflow

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

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

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; }

Relabel

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

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

演算法

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

時間複雜度

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

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

relabel：設定匯點的高度為0，源點的高度為V-1。最差的情況下，除源點和匯點外，最高的點升到了2V-3、最低的點升到了V，流不到匯點的水都回歸匯點了，如下圖所示。利用等差級數梯形公式計算一下，可以知道relabel最多會有O(V^2)次。一次relabel的時間是O(V)，所以全部的relabel的時間是O(V^2 * V) = O(V^3)。

push：當一個含水點用relabel抬高之後，最差的情況是，此點位於高處，水沿著圖上各條邊，朝著低處流──意即每次relabel之後，可能會緊接著最多O(E)次push。整個演算法最多有O(V^2)次relabel，故最多有O(V^2 * E)次push。一次push的時間是O(1)，所以全部的push的時間是O(V^2 * E * 1) = O(V^2 * E)。

歸納此三項，整個演算法需時O(V^2 * E)，受限於push的時間複雜度。

找出一個最大流＋計算最大流的權重（adjacency matix）

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

typedef int Graph[10][10]; // adjacency matrix Graph C, F; // 容量上限、流量 int d[10], e[10]; // 高度、含水點的含水量 int q[150], *qf, *qb; // 存放圖上所有除源點和匯點外的含水點 void preflow(int s, int t) { for (int j=0; j<N; ++j) if (C[s][j]) { e[j] = C[s][j]; F[s][j] = e[j]; F[j][s] = -e[j]; if (j != s && j != t) *qb++ = j; } } 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; } void relabel(int i) { for (int j=0; j<10; ++j) if (C[i][j] - F[i][j]) d[i] <?= d[j]; d[i]++; } int preflow_push_relabel(int s, int t) { memset(F, 0, sizeof(F)); memset(d, 0, sizeof(d)); memset(e, 0, sizeof(e)); qf = qb = q; d[s] = N - 1; // 設定源點高度，避免水太早灌回源點。 preflow(s, t); while (qf < qb) // 除源點匯點外還有含水點就繼續 { int i = *qf++; relabel(i); // 不一定能成功抬高此點，但無妨。 for (int j=0; j<10; ++j) if (d[i] == d[j] + 1 && C[i][j] - F[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]; }

總結

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

Ford-Fulkerson Algorithm（Augmenting Path Algorithm） v.s. Preflow-Push-Relabel Algorithm

前者推水採取深度優先，率先流到匯點；後者推水則採取廣度優先（有設定高低次序）、隨機亂推（沒有設定高低次序），率先流離源點。兩者的解題概念其實都是在嘗試推水，只是推動次序不同罷了。

百尺竿頭，更進一步

我們可以加速此演算法！

順著由高到低的順序（或者更精確點，順著admissible network之拓樸順序），慢慢推動各點的水，不要每次都一口氣推水到最低處。如此便可以避免前面章節提到的情形：「push：當一個含水點用relabel抬高之後，最差的情況是，此點位於高處，水沿著圖上各條邊，朝著低處流──意即每次relabel之後，可能會緊接著最多O(E)次push。」

不必每次都一口氣推水到最低處，可以留待以後累積足夠水量再行推水。

讀者由前面章節一路讀來，應可了解順著高低順序推水是我們的初衷，這也絕對比沒秩序亂推水還要來的省時間。為了迫使各個含水點順著整體形勢推動水，在此先設計一個「discharge」的動作。

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，
   直到所有含水點（除源點匯點）都沒水為止。
   條件：其他含水點（除源點匯點）的水，
   無法沿著目前的admissible network流入此含水點。

如果順著admissible network之拓樸順序，對各個含水點實施discharge，那麼每次relabel之後，僅需要O(V)次push。呼應本章開頭所言，整個演算法將由O(V^2 * E)變成O(V^3)。

要小心的是，當一個點進行relabel之後，會改變整張圖的admissible network，此時要謹慎選擇符合條件的含水點實施discharge。

時間複雜度

我們針對preflow、push、relabel的次數下手。preflow和relabel的時間複雜度都與先前章節相同。以下為push的時間複雜度分析：

甲、當所有點高度固定的情況下，對一個進行discharge的含水點來說，該演算法保證只會有水流出此點，並且不會有水流入此點。一個點最多擁有V-1個鄰點，故最多只會有 V-1次push。乙、一個點的高度範圍至廣為0到2V-3。丙、以上皆作用於圖上V-2個點，除去源點匯點。

由甲乙丙的乘積，可知全部的push的時間複雜度為O(V^3)。整個演算法的時間複雜度成為O(V^3)。

實作：一直找最高的含水點discharge

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

實作：含水點discharge後即排到開頭
（Relabel-to-front Algorithm）

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

實作：含水點以FIFO順序discharge
（Goldberg-Tarjan Algorithm）

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

演算法還可以再加速嗎？

當然是可以的！事實上均攤來看，一個點每次relabel之後，僅需要一兩次push就可以再relabel，然而我們的程式碼總是檢查所有的鄰邊，判斷能不能push，使得每次discharge都得花O(V)時間，而不是O(1)時間。如果我們能利用特殊的資料結構，一定可以再將演算法加速的！這就留給各位讀者去探討吧！

至於加速的極限呢？

push的次數：當一個含水點用relabel抬高之後，就得對此點進行push把水推到最低的鄰點，否則此點就無法再relabel。所以每次relabel之後最少都會有一次push，無法省略，所以push再怎麼少也有O(V^2)次。這比原先的O(V^3)次還少！另外我們還可以嘗試減少relabel次數，說不定push的次數可以少於O(V^2)次！

relabel的次數：若能避免兩個點之間反覆抬高、相互推水，而能一次抬高到定位，很有機會減少relabel的次數！

一次relabel所需的時間：目前需要以O(V)時間掃描所有鄰點，以找到最低的鄰點。如果以特殊的資料結構，更準確的知道哪個鄰點最低，就有可能加速！

Min-Cost Flow（Minimum Cost Maximum Flow）

中譯「最小成本流」、「最小費用流」。一張圖（流網路）上的每一條管線，除了有容量限制以外，還擁有單位成本──可以為正值，也可以為負值或零。現在水流流過管線時，每單位流量都會花費成本：

水流流過一條管線的成本，等於該條管線其流量與單位成本的乘積；一條小小涓流的成本，等於累加水流路徑上每一條邊其流量與單位成本的乘積；一個流的成本，等於累加圖上每一條邊其流量與單位成本的乘積。最小成本流就是指成本最小的最大流，可能會有許多個。

【註：cost在台灣譯作「成本」，詞意不太符合原意。在本章節中，讀者不妨把cost想做是「費用」（費用是對岸的譯法），水流流過管線時需要額外付出費用，儘可能的減少開銷──個人覺得此譯法比較貼近原意。】

Successive Shortest Path Algorithm

閱讀此章節之前，讀者得先了解最短路徑。可參考本站文件「Graph──Shortest Path」。

給定一張有源點和匯點的圖，找出其中一個最小成本流。限制：圖上不得有負成本環。

想法

在Ford-Fulkerson Algorithm裡頭提到：不管擴充路徑怎麼找，一定都可以達到最大流。因此，在最小成本流當中，我們只需想辦法儘量降低每一次的擴充路徑的成本，不必考慮擴充路徑的流動路線和流量大小。【待補證明】

一開始沒有負成本環，以後就沒有負成本環。

只要一開始的圖沒有負成本環，之後不管怎麼找成本最小的擴充路徑，並在剩餘容量圖上增加逆向的邊（逆向時成本也隨之變號，也就是說多了很多負成本邊），剩餘容量圖上一定仍舊沒有負成本環。

如此一來，就可以確保可以從剩餘容量圖上，一直找到源點到匯點的最短路徑。

演算法

每次都尋找一條成本最小的擴充路徑，直到找不到為止。由於溯洄沖銷後，剩餘容量圖上會多出許多負成本邊，所以要找成本最小的擴充路徑，得利用各種可處理負邊的最短路徑演算法，例如Bellman-Ford Algorithm和Floyd-Warshall Algorithm和Johnson's Algorithm。

因為剩餘容量圖上沒有負環的原故，才能用最短路徑演算法找出一條由源點到匯點的簡單路徑，做為擴充路徑；如果剩餘容量圖上有負環，最短路徑演算法找出來的就不一定是一條簡單路徑，而有可能是包含了環的路徑。一條有環的路徑，會算不出這條擴充路徑的瓶頸流量。

找出一個最小成本流＋權重＋成本（adjacency matrix）

先提供一個比較差的實作方法。

typedef int Graph[10][10]; // adjacency matrix Graph C, F, Co; // 容量上限、流量、成本 int p[10][10], d[10][10]; // 紀錄最短路徑、最短路徑長度 bool Floyd_Warshall(int s, int t) { for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) p[i][j] = j; for (int i=0; i<10; ++i) d[i] = 1e9; // 初始化Floyd-Warshall Algorithm所需的d[][]表格 for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) { // 看看能不能正向流動 if (F[i][j] < C[i][j]) d[i][j] <?= Co[i][j]; // 也看看能不能逆向沖減，成本小的比較好。 if (F[j][i] > 0) d[i][j] <?= Co[j][i]; // 由於成本為非負值， // 故逆向沖減會使擴充路徑成本減少（或不變）， // 會比正向流動使擴充路徑成本增加（或不變）來得好。 // 一旦可以逆向流動時，先考慮逆向流動一定比較好。 } // 計算成本最小的最短路徑 for (int k=0; k<10; ++k) for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k]+d[k][j]; p[i][j] = p[i][k]; } return d[s][t] !=1e9; } void MinCostMaxFlow(int s, int t) { memset(F, 0, sizeof(F)); int f = 0; c = 0; // 最大流的流量與成本 // 不斷找成本最小的擴充路徑，直到找不到為止。 while (Floyd_Warshall(s, t)) { int df = 1e9, dc = 0; // 找出擴充路徑的流量， // 也就是找到剩餘容量的瓶頸。 // 保證沒有負環。 for (int i=s, j=p[s][t]; i!=j; j=p[i=j][t]) // 如果反方向有流量， // 那麼剛剛找路徑時一定是逆向沖減， // 因為逆向沖減一定比較好。 df <?= (F[j][i] ? F[j][i] : C[i][j] - F[i][j]); // 更新擴充路徑上每一條管線的流量， // 順便計算擴充路徑的成本。 for (int i=s, j=p[s][t]; i!=j; j=p[i=j][t]) if (F[j][i]) // 如果反方向有流量， // 那麼剛剛找路徑時一定是逆向沖減， // 因為逆向沖減一定比較好。 F[j][i] -= df, dc -= Co[j][i]; else F[i][j] += df, dc += Co[i][j]; f += df; c += df * dc; } cout << "最大流的流量是" << f << endl; cout << "最小成本流的成本是" << c << endl; }

找出一個最小成本流＋權重＋成本（adjacency matrix）

可以利用Dijkstra's Algorithm以及reweighting的手段，加快演算法速度。細節就省略了，直接給程式碼。（關於reweighting可參考最短路徑的Johnson's Algorithm章節）

typedef int Graph[10][10]; // adjacency matrix Graph C, F, Co; // 容量上限、流量、成本 int p[10], d[10]; // 紀錄最短路徑樹、最短路徑長度 int h[10]; // 調權重函數 bool Dijkstra(int s, int t) { memset(p, -1, sizeof(p)); for (int i=0; i<10; ++i) d[i] = 1e9; d[s] = 0; p[s] = -s-1; // 切記：最短路徑演算法要跑過每一個點， // 不能遇到終點（匯點）就馬上結束， // 這樣會無法調整每一條邊的權重。 // （至於從源點流不到的點，就不用理它了，反正不影響流量。） // （溯洄沖減後會多出逆向的邊，不用怕沖減後會有點流不到。） for (int k=0; k<10; ++k) { int a = -1, min = 1e9; for (int i=0; i<10; ++i) if (p[i] < 0 && d[i] < min) min = d[a = i]; if (a == -1) break; p[a] = -p[a]-1; for (int i=a, j=0; j<10; ++j) { if (p[j] >= 0) continue; // 先看看能不能逆向沖減（優先考慮） // 由於成本為非負值， // 故擴充路徑的成本減少了（或不變）。 int d1 = d[i] - (Co[j][i] + h[j] - h[i]); if (F[j][i] > 0 && d1 < d[j]) d[j] = d1, p[j] = -i-1; // 再看看能不能正向流動 int d2 = d[i] + (Co[i][j] + h[i] - h[j]); if (F[i][j] < C[i][j] && d2 < d[j]) d[j] = d2, p[j] = -i-1; } } // 調整每一條邊（包含逆向沖減的邊）的權重成為非負值， // 下次依舊可以使用Dijkstra's Algorithm。 for (int i=0; i<10; ++i) if (h[i] < 1e9) // 從源點流不到的點就不理它了 h[i] += d[i]; // 累加這次的最短路徑長度即可 // 如果還能找到擴充路徑，就回傳true。 // （從源點藉由剩餘容量能夠到達匯點） return p[t] >= 0; } bool Bellman_Ford() { ......; // 略 // 調整每一條邊（包含逆向沖減的邊）的權重成為非負值， // 下次依舊可以使用Dijkstra's Algorithm。 for (int i=0; i<10; ++i) if (h[i] < 1e9) h[i] += d[i]; return p[t] >= 0; } void MinCostMaxFlow(int s, int t) { memset(F, 0, sizeof(F)); memset(h, 0, sizeof(h)); int f = 0; c = 0; // 最大流的流量與成本 // 由於一開始圖上可能有負邊， // 所以先用可以處理負邊的演算法，算出最短路徑長度， // 然後調整每一條邊的權重成為非負值。 // 之後溯洄沖減時，只要記得再調整每一條邊，保持為非負值， // 就可以一直用Dijkstra's Algorithm了。 // 不斷找成本最小的擴充路徑，直到找不到為止。 int t = 0; for (int t = 0; (t == 0 && Bellman_Ford(s, t)) || (t > 0 && Dijkstra(s, t)); ++t) { int df = 1e9, dc = 0; // 找出擴充路徑的流量， // 也就是找到剩餘容量的瓶頸。 // 保證沒有負環。 for (int j=t, i=p[t]; i!=j; i=p[j=i]) // 如果反方向有流量， // 那麼剛剛找路徑時一定是逆向沖減， // 因為逆向沖減一定比較好。 df <?= (F[j][i] ? F[j][i] : C[i][j] - F[i][j]); // 更新擴充路徑上每一條管線的流量， // 順便計算擴充路徑的成本。 for (int j=t, i=p[t]; i!=j; i=p[j=i]) if (F[j][i]) // 如果反方向有流量， // 那麼剛剛找路徑時一定是逆向沖減， // 因為逆向沖減一定比較好。 F[j][i] -= df, dc -= Co[j][i]; else F[i][j] += df, dc += Co[i][j]; f += df; c += df * dc; } cout << "最大流的流量是" << f << endl; cout << "最小成本流的成本是" << c << endl; }

UVa 10594

Primal-Dual Algorithm

給定一張有源點和匯點的圖，找出其中一個最小成本流。可以說是Successive Shortest Path Algorithm的加強版。

演算法

在Successive Shortest Path Algorithm當中，每次只找一條成本最小的擴充路徑。Primal-Dual Algorithm則是改良了前者，每次找出多條成本相等且最小的擴充路徑：

利用最短路徑長度，調整圖上所有邊的權重成為非負數之後，此時最短路徑上的邊必定會是零成本邊，而零成本邊都可能會成為最短路徑上的邊。要找出多條成本相等且最小的擴充路徑，就把圖上所有的零成本邊都找出來，然後在這些零成本邊所構成的圖當中，找最大流，便可以一次找到多條成本最小的擴充路徑。

找出一個最小成本流＋權重＋成本（adjacency matrix）

【待補程式碼】

Cycle Canceling Algorithm

給定一張有源點和匯點的圖，找出其中一個最小成本流。

在一個最大流當中，建立一條封閉的迴流，不會影響總流量，也不會違反流動的規則。只要找到一條成本為負的封閉迴流，就可以減少最大流的成本，而不會改變最大流的流量。

演算法

先嘗試找出一個最大流。然後不斷找負環，降低最大流的成本，直到找不到負環、無法降低成本為止，此時就是最小成本流。尋找負環可以使用各種可偵測負環的演算法，例如Bellman-Ford Algorithm和Label Correcting Algorithm。要找負環甚至也可以使用Minimum Mean Cycle，可加快演算法速度。

找出一個最小成本流＋權重＋成本（adjacency matrix）

【待補程式碼】

Circulation

尚未有中文翻譯，暫譯為「循環流」、「封閉流」。循環流是一個沒有源點和匯點的流，水流不斷在流網路中循環地流動，遵守所有流動的規範。一個循環流的權重（總流量），是在流網路中流動的水流流量。

Augmenting Cycle

「擴充環」。藉由剩餘容量來增加整體流量的環狀水流，其概念與Augmenting Path相同。

Flow Decomposition

循環流可以拆成很多個Augmenting Cycle。這個道理就跟源點匯點流可以拆成很多條Augmenting Path是一樣的道理。

從一個循環流拆解Augmenting Cycle的時候，最差的情況是拆出一只環的時候，僅抹除掉一條邊的流量。圖上共有E條邊，所以一個循環流最多可以拆出E個不一樣的環。

拆解完之後，便可以知道循環流的權重（總流量）。

Max-Circulation（Maximum Circulation）

權重（總流量）最大的循環流，可能有許多個。尋找最大循環流的演算法：不斷找Augmenting Cycle，直到找不到為止。

Min-Cost Circulation（Minimum Cost Maximum Circulation）

成本最小的最大循環流，可能有許多個。尋找最小成本循環流的演算法，類似於最小成本流的演算法：不斷找成本最小的Augmenting Cycle，直到找不到為止。

Flow的問題使用Circulation來解

由匯點到源點接上一條容量無限大、成本無限小的邊，所有的擴充環為了增加流量、減少成本，都會想盡辦法經過這條邊。流量的瓶頸，就會被原圖限制住，所以圖上加了邊後的最大循環流的流量，就會是原圖的最大流流量。

Circulation的問題使用Flow來解

有一種不太正確的說法是：在循環流的外部加一個獨立的源點和一個獨立的匯點。但目前我自己也還沒想到要怎麼轉換。