flow - 演算法筆記

feasible s-t flow

容量下限（流量下限）

先前只討論容量上限，並未討論容量下限。

然而，容量下限有個問題。舉例來說，當容量下限形成環，從源點流出一單位水流，即可滿足容量下限：流往環，不斷繞環，原路返回。導致「憑空出現循環水流」的弔詭現象。

大家目前沒有任何對策！因此轉為討論「循環流」：去掉源點匯點，允許憑空出現循環水流。請見後面章節「 flow 」。

feasible s-t flow （ s-t flow ）

「可行流」是符合容量限制的流。「可行流」與「流」的定義完全一樣，我們常常省略「可行」兩個字。差別在於多了「可行」之後，我們專注於「找到一個流」，而非「流量是多少」。

想要形成可行流，每條邊、每個點、每個割的流量，必須符合容量限制：

一、邊：流量，大於等於容量下限，小於等於容量上限。
二、點：入流量，大於等於出容量下限，小於等於出容量上限。
　　　　出流量，大於等於入容量下限，小於等於入容量上限。
三、割：同上。

可行流目前沒有演算法。無法處理「憑空出現循環水流」。

maximum s-t flow / minimum s-t flow

有了容量下限，除了討論「最大流」，還可以討論「最小流」。

目前沒有演算法。無法處理「憑空出現循環水流」。

minimum cost maximum s-t flow

每一條管線，除了有容量限制，還有成本（費率）。成本可以是正值（付費）、負值（補貼）、零（沒事）。水流流過管線，必須考慮費用，儘量減少開銷。

一、一段水流流過一條管線的成本：邊的流量乘以成本。

二、一道水流從源點到匯點的成本：路徑上每一條邊，流量乘以成本，求總和。

三、一個流的成本：圖上每一條邊，流量乘以成本，求總和。

「最小成本最大流」。成本最小的最大流，可能有許多個。

UVa 10594 ICPC 5095 3562 8048

minimum cost maximum s-t flow:
cycle canceling algorithm

演算法

圖上不可有負成本環，避免「憑空出現循環水流」。

一、先找一個最大流。
二、在剩餘圖上，不斷找負成本環，建立迴流降低成本。
　　直到找不到負成本環為止，即是最小成本最大流。

在一個最大流當中，建立一條封閉的迴流，不會影響總流量，也不會違反流量守恆的規則，雖然會浪費容量空間，但是有機會減少總成本。事實上可以證明，剩餘圖沒有負成本環，即是最小成本最大流，證明省略。

尋找負成本環

有三種方式！

負環：運用 Moore's algorithm 。整個演算法過程中，最多出現 C 個負成本環， C 是最大的管線容量上限；時間複雜度 O(VEC) ，偽多項式時間。

最小環：照理說是最理想的方式，可以較快達到最小成本最大流。然而，求最小環是 NP-complete 問題，時間複雜度是指數時間。

最小平均數環：意外的是個不錯的選擇。整個演算法過程中，最多出現 O(VE²logV) 個最小平均數環；時間複雜度 O(V²E³logV) ，多項式時間。證明省略。

minimum cost maximum s-t flow:
successive shortest path algorithm

演算法

圖上不可有負成本環，避免「憑空出現循環水流」。

仿照 Ford–Fulkerson algorithm ，不斷尋找成本最小的擴充路徑。證明省略。

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

一、一開始的剩餘圖沒有負成本環。

二、成本最小的擴充路徑，擴充之後讓剩餘圖增加了逆向邊（成本隨之變號，增加了負成本邊），但是剩餘圖仍舊沒有負成本環。證明省略。

如此一來，可以確保剩餘圖隨時都能實施最短路徑演算法。

尋找成本最小的擴充路徑

溯洄沖減後，剩餘圖多出許多逆向的負成本邊，因此必須採用允許負邊的最短路徑演算法，例如 Moore's algorithm 、 Floyd–Warshall algorithm 。

或者利用 Johnson's algorithm 的調整權重手法，將負邊調整為非負邊。此時成本最小的擴充路徑就會變成零成本邊，擴充之後的剩餘圖，就不會多出逆向的負成本邊，而是多出逆向的零成本邊！如此一來，就可採用不允許負邊的最短路徑演算法，例如 Dijkstra's algorithm ，降低時間複雜度。

一開始圖上可能有負成本邊，預先實施一次 Moore's algorithm 調整權重，往後就可持續使用 Dijkstra's algorithm 了。每次實施 Dijkstra's algorithm 之後，就馬上調整權重。

一、用Moore's algorithm調整權重，讓每條邊的成本為非負值。
二、不斷尋找成本最小的擴充路徑，直到找不到為止：
　甲、用Dijkstra's algorithm尋找成本最小的擴充路徑。
　乙、調整權重，讓每條邊的成本為非負值。
　丙、擴充流量。

找一條擴充路徑需時 O(V²) ，最多找 O(F) 條，時間複雜度 O(V²F) ，偽多項式時間。

找出一個最小成本最大流＋流量＋成本

// edge list + adjacency lists
// 起點、終點、剩餘容量、成本
struct Edge {int a, b, r, w;} edge[1000];
int en = 0;
vector<int> adj[10];
void addedge(int a, int b, int c, int w)
{
// 加入一條邊
edge[en] = (Edge){a, b, c, +w};
adj[a].push_back(en++);
// 同時也加入反向邊
edge[en] = (Edge){b, a, 0, -w};
adj[b].push_back(en++);
}
// Moore's algorithm
int p[10], d[10]; // 最短路徑樹、最短路徑長度
int index[10]; // 最短路徑樹對應的邊的索引值
bool inqueue[10]; // 記錄各個點是否在queue當中
void MinCostMaxstFlow(int s, int t)
{
int flow = 0, cost = 0; // 最小成本最大流的流量與成本
while (true)
{
// 實施Moore's algorithm，
// 從剩餘圖上面，找到成本最小的擴充路徑。
for (int i=0; i<10; ++i) d[i] = 1e9;
d[s] = 0;
queue<int> Q;
Q.push(s);
// inqueue[s] = true;
while (!Q.empty())
{
int a = Q.front(); Q.pop();
inqueue[a] = false;
for (int i=0; i<adj[a].size(); ++i)
{
Edge& e = edge[adj[a][i]];
int b = e.b;
if (e.r > 0 && d[a] + e.w < d[b])
{
d[b] = d[a] + e.w;
p[b] = a;
index[b] = adj[a][i];
if (!inqueue[b])
{
Q.push(b);
inqueue[b] = true;
}
}
}
}
// 已經找不到擴充路徑
if (d[t] == 1e9) break;
// 計算擴充路徑的流量，並且進行擴充。
int df = 1e9;
for (int a = t; a != s; a = p[a])
{
int i = index[a];
df = min(df, edge[i].r);
}
for (int a = t; a != s; a = p[a])
{
int i = index[a];
edge[i].r -= df;
edge[i^1].r += df;
}
flow += df;
cost += df * d[t];
}
cout << "最大流的流量是" << flow;
cout << "最小成本最大流的成本是" << cost;
}

typedef int Graph[10][10]; // adjacency matrix
Graph C, F, W; // 容量上限、流量、成本
int p[10][10], d[10][10]; // 記錄最短路徑、最短路徑長度
bool floyd_warshall(int s, int t)
{
/* 初始化Floyd–Warshall algorithm */
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][i] = 1e9;
for (int i=0; i<10; ++i)
for (int j=0; j<10; ++j)
{
// 看看能不能正向流動
if (F[i][j] < C[i][j])
d[i][j] = min(d[i][j], W[i][j]);
// 也看看能不能逆向沖減，成本越小越好。
if (F[j][i] > 0)
d[i][j] = min(d[i][j], W[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];
}
/* 找到擴充路徑，就回傳true。 */
return d[s][t] != 1e9;
}
void MinCostMaxstFlow(int s, int t)
{
memset(F, 0, sizeof(F));
int flow = 0, cost = 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 = min(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 -= W[j][i];
else
F[i][j] += df, dc += W[i][j];
flow += df;
cost += df * dc;
}
cout << "最大流的流量是" << flow;
cout << "最小成本最大流的成本是" << cost;
}

typedef int Graph[10][10]; // adjacency matrix
Graph C, F, W; // 容量上限、流量、成本
int p[10], d[10]; // 最短路徑樹、最短路徑長度
int h[10]; // 調權重函數
bool dijkstra(int s, int t)
{
/* 初始化Dijkstra's algorithm */
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] - (W[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] + (W[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;
}
void MinCostMaxstFlow(int s, int t)
{
memset(F, 0, sizeof(F));
memset(h, 0, sizeof(h));
int flow = 0, cost = 0; // 最小成本最大流的流量與成本
// 不斷找成本最小的擴充路徑，直到找不到為止。
// （假設一開始就沒有負成本邊，不必先調整權重。）
while (dijkstra(s, t))
{
int df = 1e9, dc = 0;
// 計算可以擴充的流量大小
for (int j=t, i=p[t]; i!=j; i=p[j=i])
// 因為逆向沖減可以降低（或不變）擴充路徑的成本，
// 所以如果逆向有流量，
// 那麼剛剛找路徑時一定是逆向沖減。
df = min(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 -= W[j][i];
else
F[i][j] += df, dc += W[i][j];
flow += df;
cost += df * dc;
}
cout << "最大流的流量是" << flow;
cout << "最小成本最大流的成本是" << cost;
}

minimum cost maximum s-t flow:
primal–dual algorithm

演算法

圖上不可有負成本環，避免「憑空出現循環水流」。

仿照 blocking flow algorithm ，每回合找到全部的成本最小的擴充路徑。

利用最短路徑長度，調整圖上所有邊的權重成為非負數之後，此時最短路徑上的邊就是零成本邊。在零成本邊所構成的圖當中，找最大流，便可以一次找到全部的成本最小的擴充路徑。

時間複雜度我也不知道。

flow

註記

flow 與 s-t flow 是兩個不同的概念。然而古代人當初定義問題時，卻將兩者都稱作 flow ，從此之後便混淆不清了。

cut 與 s-t cut 亦有類似情況。古代人當初沒有 cut 的概念，將 s-t cut 直接稱作 cut 。不過自從有人發表 cut 的演算法之後，眾人便開始注重用詞了。

以下章節， flow 譯作「流」或「循環流」， s-t flow 譯作「源匯流」。

flow

從現在起，水流不再從源點流到匯點，水流改為不斷循環。

要計算總流量，可將水流分解成數個環，以環流量的總和作為總流量。每次挑一條有水流的邊開始尋找環，最多分解成 E 個環。

supply / demand

「供點」有水注入、「需點」有水洩出，彷彿源點與匯點。圖上可以有多個供點與需點，供水量總和必須等於需水量總和，才有機會形成可行流。

圖上每一點皆有供需水量： supply 的供需水量為正值，該點流出多於流入； demand 的供需水量為負值，該點流入多於流出；其他的點的供需水量為零，流入等於流出。

供需水量 = 流出水量 - 流入水量

導入 supply 與 demand 之後，總流量的定義就不明確了。這裡姑且定義成： supply 的總和，再加上不受 supply 與 demand 影響的循環流流量。

最大流最小割定理、可行流定理

導入水流流量：任意一個割，甲側流往乙側的水量總和，等於乙側流往甲側的水量總和。

導入容量上限：任意一個割，甲側流往乙側的水量總和，小於等於甲側到乙側的容量總和。最大流流量，小於等於任何一個「管線容量的最小 s-t 割」！

導入供需水量：任意一個割，甲側的供需水量總和，必須小於等於甲側到乙側的容量總和，才能形成可行流。

導入容量下限：任意一個割，甲側到乙側的容量下限總和，必須小於等於甲側到乙側的容量上限總和、也要小於等於乙側到甲側的容量上限總和，才能形成可行流。

容量下限變成零

有向邊的容量下限，得移轉至 supply 與 demand 。

預先流水，水量等於容量下限：

必須記錄每條邊的預流水量與耗費成本，以利之後還原。

容量上限變成無限大

其實沒有必要移除容量上限 ── 最大流演算法皆支援容量上限。不過還是介紹一下吧。

移除容量下限後，可以進一步移除容量上限。容量上限添加至終點，然後回沖：

移除容量上限後，變成二分圖，得以設計更簡潔的資料結構與演算法。

負成本變成正成本

運用溯洄沖減，可以把負成本變成正成本。

預先流水，水量等於容量上限：

必須記錄每條邊的預流水量和耗費成本，以利之後還原。

無向邊變成有向邊

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

成本非負、沒有容量下限：為了降低成本，來回水流可以變成單向水流。上述兩條方向相反的有向邊，大可不必共用容量上限，宛如普通的有向邊。

成本非負、擁有容量下限：預先在無向邊上來回流動，滿足容量下限。流量是容量下限的一半，可以是 0.5 。如果流量只能是整數，則可以類比為 0/1 knapsack problem ，屬於 NP-complete 問題。

成本為負：同上。流量是實數，就來回流動。流量是整數， NP-complete 。

歸約

feasible s-t flow -> feasible flow -> maximum s-t flow
導入成本，依然如此。

可行源匯流化作可行循環流。匯點到源點增加一條管線，容量上限無限大（圖上所有邊的容量上限總和），成本無限小。

可行循環流化作最大源匯流。新增源點與匯點，源點接至 supply ，容量上限為供水量； demand 接至匯點，容量上限為需水量。然後嘗試求最大源匯流，若源點管線與匯點管線皆滿溢，則有可行循環流，反之則無。拆除新增管線，最大源匯流就變成可行循環流。

總結

流的問題總是可以簡化成：有容量上限、無容量下限、成本非負、有向邊，許多 supply 和 demand 。

無論流動方式是循環流、源匯流，無論最佳化目標是最大流、最小流、可行流，都可以歸約成 minimum cost maximum s-t flow 。

UVa 11647 1259 ICPC 3787 4722 5131

feasible flow

「可行流」。符合供需水量、容量上下限的流。

直覺的方式，就是歸約。進階的方式，就是瞭解歸約過程之後，直接以原圖實施計算，不歸約、不改圖。

承襲 maximum s-t flow 演算法，額外考慮 flow 、 supply 、 demand 等新概念。

不斷尋找起點為 supply 、終點為 demand 的擴充路徑，進行擴充後就根據水量減損 supply 、增益 demand ，直到圖上沒有 supply 與 demand 為止。

maximum flow

「最大流」。流量最大的可行流。

一、首先隨便找出一個可行流，然後不斷找擴充環。

根據最大流最小割定理，剩餘圖沒有擴充環，即是最大流。

二、窮舉所有兩點之間容量 s-t 割，取最小值。【尚待確認】

minimum flow

「最小流」。流量最小的可行流。

一、擴充路徑堅持使用點互斥路徑，即得最小流。【尚待確認】

二、首先隨便找出一個可行流，然後不斷消去擴充環。【尚待確認】

我找不到任何有關最小流的正確性證明！

minimum cost flow

「最小成本流」。成本最小的可行流。

承襲 minimum cost maximum s-t flow 演算法。

cycle canceling algorithm ：先找到任意一個可行流，再以負成本環進行擴充。

successive shortest path algorithm 與 primal–dual algorithm ：不斷尋找起點為 excess 、終點為 deflict 、成本最小的擴充路徑，直到所有 excess 與 deflict 成為零。如果 excess 與 deflict 沒有同時成為零，則沒有可行流。

excess / deficit

「積水點」水量超出平衡，「缺水點」水量低於平衡。當圖上有 excess 與 deficit ，表示流量不平衡，不是可行流。

積缺水量 = 流入水量 - 流出水量 + 供需水量

multi-commodity flow

k vertex-disjoint paths
k edge-disjoint paths

給定 k 組起點與終點，找齊 k 條路徑，點（邊）皆相異；除了起點與終點。可能找不到。

flow 問題，源點與匯點不必對應， P 問題。

此問題，起點與終點必須對應， NP-complete 問題。

差別在於交叉路徑。 flow 問題，運用溯洄沖減，交叉路徑總是變成不交叉路徑。此問題則不然。

UVa 11301

k vertex-disjoint s-t paths
k edge-disjoint s-t paths

給定一組起點與終點，找出 k 條路徑，點（邊）皆相異；除了起點與終點。起點都是同一點、終點都是同一點，無所謂對不對應。可能找不到。

解法是 maximum s-t flow 。

UVa 10806 ICPC 4259 4271

進階版本，這 k 條路徑的權重總和必須最小。

解法是 minimum cost maximum s-t flow 。

UVa 11823 1236 ICPC 3570

multi-commodity flow

指定多組供點、需點，必須對應。

流量是實數， P 問題。流量是整數， NP-complete 問題，大家改為研究速度飛快的近似演算法。