flow
feasible s-t flow
minimum cost maximum s-t flow
minimum cost maximum s-t flow:
cycle canceling algorithm
minimum cost maximum s-t flow:
successive shortest path algorithm
minimum cost maximum s-t flow:
primal–dual algorithm
flow
multi-commodity 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

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) ,偽多項式時間。

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

  1. // edge list + adjacency lists
  2. // 起點、終點、剩餘容量、成本
  3. struct Edge {int a, b, r, w;} edge[1000];
  4. int en = 0;
  5. vector<int> adj[10];
  6. void addedge(int a, int b, int c, int w)
  7. {
  8. // 加入一條邊
  9. edge[en] = (Edge){a, b, c, +w};
  10. adj[a].push_back(en++);
  11. // 同時也加入反向邊
  12. edge[en] = (Edge){b, a, 0, -w};
  13. adj[b].push_back(en++);
  14. }
  15. // Moore's algorithm
  16. int p[10], d[10]; // 最短路徑樹、最短路徑長度
  17. int index[10]; // 最短路徑樹對應的邊的索引值
  18. bool inqueue[10]; // 記錄各個點是否在queue當中
  19. void MinCostMaxstFlow(int s, int t)
  20. {
  21. int flow = 0, cost = 0; // 最小成本最大流的流量與成本
  22. while (true)
  23. {
  24. // 實施Moore's algorithm,
  25. // 從剩餘圖上面,找到成本最小的擴充路徑。
  26. for (int i=0; i<10; ++i) d[i] = 1e9;
  27. d[s] = 0;
  28. queue<int> Q;
  29. Q.push(s);
  30. // inqueue[s] = true;
  31. while (!Q.empty())
  32. {
  33. int a = Q.front(); Q.pop();
  34. inqueue[a] = false;
  35. for (int i=0; i<adj[a].size(); ++i)
  36. {
  37. Edge& e = edge[adj[a][i]];
  38. int b = e.b;
  39. if (e.r > 0 && d[a] + e.w < d[b])
  40. {
  41. d[b] = d[a] + e.w;
  42. p[b] = a;
  43. index[b] = adj[a][i];
  44. if (!inqueue[b])
  45. {
  46. Q.push(b);
  47. inqueue[b] = true;
  48. }
  49. }
  50. }
  51. }
  52. // 已經找不到擴充路徑
  53. if (d[t] == 1e9) break;
  54. // 計算擴充路徑的流量,並且進行擴充。
  55. int df = 1e9;
  56. for (int a = t; a != s; a = p[a])
  57. {
  58. int i = index[a];
  59. df = min(df, edge[i].r);
  60. }
  61. for (int a = t; a != s; a = p[a])
  62. {
  63. int i = index[a];
  64. edge[i].r -= df;
  65. edge[i^1].r += df;
  66. }
  67. flow += df;
  68. cost += df * d[t];
  69. }
  70. cout << "最大流的流量是" << flow;
  71. cout << "最小成本最大流的成本是" << cost;
  72. }
  1. typedef int Graph[10][10]; // adjacency matrix
  2. Graph C, F, W; // 容量上限、流量、成本
  3. int p[10][10], d[10][10]; // 記錄最短路徑、最短路徑長度
  4. bool floyd_warshall(int s, int t)
  5. {
  6. /* 初始化Floyd–Warshall algorithm */
  7. for (int i=0; i<10; ++i)
  8. for (int j=0; j<10; ++j)
  9. p[i][j] = j;
  10. for (int i=0; i<10; ++i)
  11. d[i][i] = 1e9;
  12. for (int i=0; i<10; ++i)
  13. for (int j=0; j<10; ++j)
  14. {
  15. // 看看能不能正向流動
  16. if (F[i][j] < C[i][j])
  17. d[i][j] = min(d[i][j], W[i][j]);
  18. // 也看看能不能逆向沖減,成本越小越好。
  19. if (F[j][i] > 0)
  20. d[i][j] = min(d[i][j], W[j][i]);
  21. // 由於成本為非負值,
  22. // 逆向沖減會降低(或不變)擴充路徑的成本,
  23. // 正向流動會提高(或不變)擴充路徑的成本,
  24. // 一旦可以逆向沖減時,先考慮逆向沖減一定比較好。
  25. }
  26. /* 在剩餘圖上,計算出一條成本最小的擴充路徑。 */
  27. for (int k=0; k<10; ++k)
  28. for (int i=0; i<10; ++i)
  29. for (int j=0; j<10; ++j)
  30. if (d[i][k] + d[k][j] < d[i][j])
  31. {
  32. d[i][j] = d[i][k] + d[k][j];
  33. p[i][j] = p[i][k];
  34. }
  35. /* 找到擴充路徑,就回傳true。 */
  36. return d[s][t] != 1e9;
  37. }
  38. void MinCostMaxstFlow(int s, int t)
  39. {
  40. memset(F, 0, sizeof(F));
  41. int flow = 0, cost = 0; // 最小成本最大流的流量與成本
  42. // 不斷找成本最小的擴充路徑,直到找不到為止。
  43. while (floyd_warshall(s, t))
  44. {
  45. int df = 1e9, dc = 0;
  46. // 計算可以擴充的流量大小
  47. for (int i=s, j=p[s][t]; i!=j; j=p[i=j][t])
  48. // 因為逆向沖減可以降低(或不變)擴充路徑的成本,
  49. // 所以如果逆向有流量,
  50. // 那麼剛剛找路徑時一定是逆向沖減。
  51. df = min(df, (F[j][i] ? F[j][i] : C[i][j] - F[i][j]));
  52. // 進行擴充,順便計算成本。
  53. for (int i=s, j=p[s][t]; i!=j; j=p[i=j][t])
  54. if (F[j][i])
  55. // 因為逆向沖減可以降低(或不變)擴充路徑的成本,
  56. // 所以如果逆向有流量,
  57. // 那麼剛剛找路徑時一定是逆向沖減。
  58. F[j][i] -= df, dc -= W[j][i];
  59. else
  60. F[i][j] += df, dc += W[i][j];
  61. flow += df;
  62. cost += df * dc;
  63. }
  64. cout << "最大流的流量是" << flow;
  65. cout << "最小成本最大流的成本是" << cost;
  66. }
  1. typedef int Graph[10][10]; // adjacency matrix
  2. Graph C, F, W; // 容量上限、流量、成本
  3. int p[10], d[10]; // 最短路徑樹、最短路徑長度
  4. int h[10]; // 調權重函數
  5. bool dijkstra(int s, int t)
  6. {
  7. /* 初始化Dijkstra's algorithm */
  8. memset(p, -1, sizeof(p));
  9. for (int i=0; i<10; ++i) d[i] = 1e9;
  10. /* 在剩餘圖上,計算出一條成本最小的擴充路徑。 */
  11. d[s] = 0; p[s] = -s-1;
  12. // 切記:最短路徑演算法要跑過每一個點,
  13. // 不能遇到終點(匯點)就馬上結束,
  14. // 這樣會無法調整每一條邊的權重。
  15. // (至於從源點流不到的點,就不用理它了,反正不影響流量。)
  16. // (溯洄沖減後會多出逆向邊。原先流得到的點,沖減之後還是流得到。)
  17. for (int k=0; k<10; ++k)
  18. {
  19. int a = -1, min = 1e9;
  20. for (int i=0; i<10; ++i)
  21. if (p[i] < 0 && d[i] < min)
  22. min = d[a = i];
  23. if (a == -1) break;
  24. p[a] = -p[a]-1;
  25. for (int i=a, j=0; j<10; ++j)
  26. {
  27. if (p[j] >= 0) continue;
  28. // 先嘗試逆向沖減,可以降低(或不變)成本。
  29. int d1 = d[i] - (W[j][i] + h[j] - h[i]);
  30. if (F[j][i] > 0 && d1 < d[j])
  31. d[j] = d1, p[j] = -i-1;
  32. // 再嘗試正向流動
  33. int d2 = d[i] + (W[i][j] + h[i] - h[j]);
  34. if (F[i][j] < C[i][j] && d2 < d[j])
  35. d[j] = d2, p[j] = -i-1;
  36. }
  37. }
  38. /* 調整剩餘圖的每一條邊(包括逆向邊)的權重成為非負值,
  39. 下次就又可以使用Dijkstra's algorithm了。 */
  40. for (int i=0; i<10; ++i)
  41. if (h[i] < 1e9) // 從源點流不到的點就不理它了
  42. h[i] += d[i]; // 累加這次的最短路徑長度即可
  43. /* 找到擴充路徑,就回傳true。 */
  44. return p[t] >= 0;
  45. }
  46. void MinCostMaxstFlow(int s, int t)
  47. {
  48. memset(F, 0, sizeof(F));
  49. memset(h, 0, sizeof(h));
  50. int flow = 0, cost = 0; // 最小成本最大流的流量與成本
  51. // 不斷找成本最小的擴充路徑,直到找不到為止。
  52. // (假設一開始就沒有負成本邊,不必先調整權重。)
  53. while (dijkstra(s, t))
  54. {
  55. int df = 1e9, dc = 0;
  56. // 計算可以擴充的流量大小
  57. for (int j=t, i=p[t]; i!=j; i=p[j=i])
  58. // 因為逆向沖減可以降低(或不變)擴充路徑的成本,
  59. // 所以如果逆向有流量,
  60. // 那麼剛剛找路徑時一定是逆向沖減。
  61. df = min(df, (F[j][i] ? F[j][i] : C[i][j] - F[i][j]));
  62. // 更新擴充路徑上每一條管線的流量,
  63. // 順便計算擴充路徑的成本。
  64. for (int j=t, i=p[t]; i!=j; i=p[j=i])
  65. if (F[j][i])
  66. // 因為逆向沖減可以降低(或不變)擴充路徑的成本,
  67. // 所以如果逆向有流量,
  68. // 那麼剛剛找路徑時一定是逆向沖減。
  69. F[j][i] -= df, dc -= W[j][i];
  70. else
  71. F[i][j] += df, dc += W[i][j];
  72. flow += df;
  73. cost += df * dc;
  74. }
  75. cout << "最大流的流量是" << flow;
  76. cout << "最小成本最大流的成本是" << cost;
  77. }

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 問題,大家改為研究速度飛快的近似演算法。