跳转至

Stoer–Wagner 算法

定義

由於取消了 源匯點 的定義，我們需要對 割 的概念進行重定義。

（其實是網絡流部分有關割的定義與維基百科不符，只是由於一般接觸到的割都是「有源匯的最小割問題」，因此這個概念也就約定俗成了。）

割

去掉其中所有邊能使一張網絡流圖不再連通（即分成兩個子圖）的邊集稱為圖的割。

即：在無向圖 \(G = (V, E)\) 中，設 \(C\) 為圖 \(G\) 中一些弧的集合，若從 \(G\) 中刪去 \(C\) 中的所有弧能使圖 \(G\) 不是連通圖，稱 \(C\) 圖 \(G\) 的一個割。

有源匯點的最小割問題

同 最小割 中的定義。

無源匯點的最小割問題

包含的弧的權和最小的割。也稱為全局最小割。

顯然，直接跑網絡流的複雜度是行不通的。

Stoer–Wagner 算法

引入

Stoer–Wagner 算法在 1995 年由Mechthild Stoer與Frank Wagner提出，是一種通過 遞歸 的方式來解決 無向正權圖 上的全局最小割問題的算法。

性質

算法複雜度 \(O(|V||E| + |V|^{2}\log|V|)\) 一般可近似看作 \(O(|V|^3)\)。

它的實現基於以下基本事實：設圖 \(G\) 中有任意兩點 \(S, T\)。那麼任意一個圖 \(G\) 的割 \(C\)，或者有 \(S, T\) 在同一連通塊中，或者有 \(C\) 是一個 \({S-T}\) 割。

過程

  1. 在圖 \(G\) 中任意指定兩點 \(s, t\)，並且以這兩點作為源匯點求出圖 \(G\) 的 \(S-T\) 最小割（定義為cut of phase），更新當前答案。
  2. 「合併」點 \(s, t\)，如果圖 \(G\) 中 \(|V|\) 大於 \(1\)，則回到第一步。
  3. 輸出所有cut of phase的最小值。

合併兩點 \(s, t\)：刪除 \(s, t\) 之間的連邊 \((s, t)\)，對於 \(G/\{s, t\}\) 中任意一點 \(k\)，刪除 \((t, k)\)，並將其邊權 \(d(t, k)\) 加到 \(d(s, k)\) 上

解釋：如果 \(s, t\) 在同一連通塊，對於 \(G/\{s, t\}\) 中的一點 \(k\)，假如 \((k, s) \in C_{\min}\)，那麼 \((k, t) \in C_{\min}\) 也一定成立，否則因為 \(s, t\) 連通，\(k, t\) 連通，導致 \(s, k\) 在同一連通塊，此時 \(C = C_{\min} / {s}\) 將比 \(C_{\min}\) 更優。反之亦然。所以 \(s, t\) 可以看作同一點。

步驟 1 考慮了 \(s,t\) 不在同一連通塊的情形，步驟 2 考慮了剩餘的情況。由於每次執行步驟 2 都會使 \(|V|\) 減小 \(1\)，因此算法將在進行 \(|V| - 1\) 後結束。

S-T 最小割的求法

（顯然不是網絡流。）

假設進行若干次合併以後，當前圖 \(G'=(V', E')\)，執行步驟 1。

我們構造一個集合 \(A\)，初始時令 \(A = \varnothing\)。

我們每次將 \(V'\) 中所有點中，滿足 \(i \notin A\)，且權值函數 \(w(A, i)\) 最大的節點加入集合 \(A\)，直到 \(|A| = |V'|\)。

其中權值函數的定義：

\(w(A, i) = \sum_{j \in A} d(i, j)\)

（若 \((i, j) \notin E'\)，則 \(d(i, j) = 0\)）。

容易知道所有點加入 \(A\) 的順序是固定的，令 \(\operatorname{ord}(i)\) 表示第 \(i\) 個加入 \(A\) 的點，\(t = \operatorname{ord}(|V'|)\)；\(\operatorname{pos}(v)\) 表示 \(v\) 被加入 \(A\) 後 \(|A|\) 的大小，即 \(v\) 被加入的順序。

則對任意點 \(s\)，一個 \(s\) 到 \(t\) 的割即為 \(w(t)\)。

證明

定義一個點 \(v\) 被激活，當且僅當 \(v\) 在加入 \(A\) 中時，發現在 \(A\) 此時最後一個點 \(u\) 早於 \(v\) 加入集合，並且在圖 \(G'' = (V', E'/C)\) 中，\(u\) 與 \(v\) 不在同一連通塊。

Stoer-Wagner1

如圖，藍色區域和黃色區域為兩個不同的連通塊，方括號中的數字為加入 \(A\) 的順序。灰色節點為活躍節點，白色節點則不是活躍節點。

定義 \(A_v = \{u \mid \operatorname{pos}(u) < \operatorname{pos}(v)\}\)，也就是嚴格早於 \(v\) 加入 \(A\) 的點，令 \(E_v\) 為 \(E'\) 的誘導子圖（點集為 \(A_v \cup\{v\}\)）的邊集。（注意包含點 \(v\)。）

定義誘導割 \(C_v\) 為 \(C \cap E_v\)。\(w(C_v) = \sum_{(i,j) \in C_v} d(i, j)\)。

Lemma 1

對於任何被激活的點 \(v\)，\(w(A_v, v) \le w(C_v)\)。

證明：使用數學歸納法。

對於第一個被激活的點 \(v_0\)，由定義可知 \(w(A_{v_0}, v_0) = w(C_{v_0})\)。

對於之後兩個被激活的點 \(u, v\)，假設 \(\operatorname{pos}(v) < \operatorname{pos}(u)\)，則有：

\(w(A_u, u) = w(A_v, u) + w(A_u - A_v, u)\)

又，已知：

\(w(A_v, u) \le w(A_v, v)\) 並且 \(w(A_v, v) \le w(C_v)\) 聯立可得：

\(w(A_u, u) \le w(C_v) + w(A_u - A_v, u)\)

由於 \(w(A_u - A_v, u)\) 對 \(w(C_u)\) 有貢獻而對 \(w(C_v)\) 沒有貢獻，在所有邊均為正權的情況下，可導出：

\(w(A_u,u) \le w(C_u)\)

由歸納法得證。

由於 \(\operatorname{pos}(s) < \operatorname{pos}(t)\)，並且 \(s, t\) 不在同一連通塊，因此 \(t\) 會被激活，由此可以得出 \(w(A_t, t) \le w(C_t) = w(C)\)。

P5632【模板】Stoer–Wagner 算法 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
const int N = 601;
int fa[N], siz[N], edge[N][N];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int dist[N], vis[N], bin[N];
int n, m;

int contract(int &s, int &t) {  // Find s,t
  memset(dist, 0, sizeof(dist));
  memset(vis, false, sizeof(vis));
  int i, j, k, mincut, maxc;
  for (i = 1; i <= n; i++) {
    k = -1;
    maxc = -1;
    for (j = 1; j <= n; j++)
      if (!bin[j] && !vis[j] && dist[j] > maxc) {
        k = j;
        maxc = dist[j];
      }
    if (k == -1) return mincut;
    s = t;
    t = k;
    mincut = maxc;
    vis[k] = true;
    for (j = 1; j <= n; j++)
      if (!bin[j] && !vis[j]) dist[j] += edge[k][j];
  }
  return mincut;
}

const int inf = 0x3f3f3f3f;

int Stoer_Wagner() {
  int mincut, i, j, s, t, ans;
  for (mincut = inf, i = 1; i < n; i++) {
    ans = contract(s, t);
    bin[t] = true;
    if (mincut > ans) mincut = ans;
    if (mincut == 0) return 0;
    for (j = 1; j <= n; j++)
      if (!bin[j]) edge[s][j] = (edge[j][s] += edge[j][t]);
  }
  return mincut;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  if (m < n - 1) {
    cout << 0;
    return 0;
  }
  for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
  for (int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w;
    int fu = find(u), fv = find(v);
    if (fu != fv) {
      if (siz[fu] > siz[fv]) swap(fu, fv);
      fa[fu] = fv, siz[fv] += siz[fu];
    }
    edge[u][v] += w, edge[v][u] += w;
  }
  int fr = find(1);
  if (siz[fr] != n) {
    cout << 0;
    return 0;
  }
  cout << Stoer_Wagner();
  return 0;
}

複雜度分析與優化

contract操作的複雜度為 \(O(|E| + |V|\log|V|)\)。

一共進行 \(O(|V|)\) 次contract，總複雜度為 \(O(|E||V| + |V|^2\log|V|)\)。

根據 最短路 的經驗，算法瓶頸在於找到權值最大的點。

在一次contract中需要找 \(|V|\) 次堆頂，並遞增地修改 \(|E|\) 次權值。

斐波那契堆 可以勝任 \(O(\log|V|)\) 查找堆頂和 \(O(1)\) 遞增修改權值的工作，理論複雜度可以達到 \(O(|E| + |V|\log|V|)\)，但是由於斐波那契堆常數過大，碼量高，實際應用價值偏低。

（實際測試中開 O2 還要卡評測波動才能過。）

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：DanJoshua, opsiff, yzy-1
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用