

Stoer-Wagner 算法

概念¶

由于取消了 源汇点 的定义，我们需要对割的概念进行重定义。

（其实是网络流部分有关割的定义与维基百科不符，只是由于一般接触到的割都是「有源汇的最小割问题」，因此这个概念也就约定俗成了。）

割¶

去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割。

即：在无向图中，设为图中一些弧的集合，若从中删去中的所有弧能使图不是连通图，称图的一个割。

有源汇点的最小割问题¶

同最小割中的定义。

无源汇点的最小割问题¶

包含的弧的权和最小的割。也称为全局最小割。

显然，直接跑网络流的复杂度是行不通的。

Stoer-Wagner 算法¶

Stoer-Wagner 算法在 1995 年由Mechthild Stoer与Frank Wagner提出，是一种通过递归的方式来解决 无向正权图 上的全局最小割问题的算法。算法复杂度一般可近似看作。

它的实现基于以下基本事实：设图中有任意两点。那么任意一个图的割，或者有在同一连通块中，或者有是一个割。

算法流程¶

在图中任意指定两点，并且以这两点作为源汇点求出图的最小割（定义为cut of phase），更新当前答案。
「合并」点，如果图中大于，则回到第一步。
输出所有cut of phase的最小值。

合并两点：删除之间的连边，对于中任意一点，删除，并将其边权加到上

解释：如果在同一连通块，对于中的一点，假如，那么也一定成立，否则因为连通，连通，导致在同一连通块，此时将比更优。反之亦然。所以可以看作同一点。

步骤 1 考虑了不在同一连通块的情形，步骤 2 考虑了剩余的情况。由于每次执行步骤 2 都会使减小，因此算法将在进行后结束。

S-T 最小割的求法¶

（显然不是网络流。）

假设进行若干次合并以后，当前图，执行步骤 1。

我们构造一个集合，初始时令。

我们每次将中所有点中，满足，且权值函数最大的节点加入集合，直到。

其中权值函数的定义：

（若，则）。

容易知道所有点加入的顺序是固定的，令表示第个加入的点，；表示被加入后的大小，即被加入的顺序。

则对任意点，一个到的割即为。

证明算法正确性¶

定义一个点被激活，当且仅当在加入中时，发现在存在一个点早于加入集合，并且在图中，与不在同一连通块。

定义，也就是严格早于加入的点，令为的诱导子图（点集为）的边集。（注意包含点。）

定义诱导割为。。

Lemma 1

对于任何被激活的点，。

证明：使用数学归纳法。

对于第一个被激活的点，由定义可知。

对于之后两个被激活的点，假设，则有：

又，已知：

并且联立可得：

由于对有贡献而对没有贡献，在所有边均为正权的情况下，可导出：

由归纳法得证。

由于，并且不在同一连通块，因此会被激活，由此可以得出。

P5632 【模板】Stoer-Wagner算法

  #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操作的复杂度为。

一共进行次contract，总复杂度为。

根据最短路的经验，算法瓶颈在于找到权值最大的点。

在一次contract中需要找次堆顶，并递增地修改次权值。

斐波那契堆可以胜任查找堆顶和递增修改权值的工作，理论复杂度可以达到，但是由于斐波那契堆常数过大，码量高，实际应用价值偏低。

（实际测试中开 O2 还要卡评测波动才能过。）

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