POJ2914 Lutece 2710 Minimum Cut

13 April 2022 | duanyll | Tags: OI 题解图论

题意

$n\leq 500$ 个点 $m$ 条边（最多完全图）的带权无向图，问至少删去的边权之和，使删边后图不连通。（任意两点的最小割）。

分析

显然枚举两点用最大流最小割来求跑不过。介绍此类问题的模板做法：Stoer-Wagner 算法，主要思想是枚举寻找任意两点的最小割，每处理两点之后进行“缩点”操作，可保证 $O(n^3)$ 复杂度。

考虑 $G$ 的最小割把 $G$ 分割为两侧，则枚举两点 $u,v$ 一定属于一下两种情况：

$u, v$ 不在同一侧，那么枚举到 $u, v$ 时就能求出答案。
$u, v$ 在同一侧，那么可以进行缩点操作，把 $u,v$ 合并成一个点，不会影响答案。

只需要给定起点时能够 $O(n^2)$ 求出最小割，然后不断删掉（合并）一个点再进行 $O(n^2)$ 的枚举，最终可达到 $O(n^3)$ 的复杂度。

由于具有缩点的特性，可以考虑类似 Prim 的做法，不断向一个点集中加点，这个点集对应最终最小割方案的一侧，而最小割另一侧已经通过缩点过程被缩成了一个点，于是只需要用 w[i] 数组来维护每个点集外的点到点集的直接连边边权之和。不断地选取当前 w[i] 最大的点加入点集中，最终选取的点的 w[v] 值就对应一种合法、并且最优的‘单点’最小割方案。

此时即可统计答案，然后缩点，再进行下一次类 Prim 枚举。缩点时应该考虑将最终剩下的 $v$ （一定要合并 $v$，下一次从头枚举才是有意义的，否则找到的最终点还是 $v$）和上一次添加进点集的点 $u$ 进行合并，容易贪心证明此种合并方式的最优性。

为了合并操作的方便，使用邻接矩阵存图，可以用下面的 for 循环完成缩点：

for (int i = 1; i <= remain; i++) {
    if (i == u || i == v) continue;
        g[i][u] += g[i][v];
        g[u][i] += g[v][i];
}

然后只需删除 $v$，使得之后不再枚举它。下文代码中利用 fa 数组删除 $v$ 是一种巧妙的实现方式。

代码

int g[MAXN][MAXN];
int w[MAXN]; // w[i] 已选定集合中所有点到 i 的直接连边边权总和
int fa[MAXN]; // 处理合并操作后，删掉其中一个点
bool ins[MAXN];

int main() {
    int n, m;
    while (cin >> n >> m) {
        memset(g, 0, sizeof g);
        for (int i = 1; i <= m; i++) {
            int u = read();
            int v = read();
            int c = read();
            g[u][v] += c;
            g[v][u] += c;
        }
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
        int ans = INF;
        int remain = n;
        while (remain > 1) {
            memset(w, 0, sizeof w);
            memset(ins, false, sizeof ins);
            ins[0] = true;
            int u = 0;
            int v = 0;
            for (int i = 1; i < remain; i++) {
                u = v;
                v = -1;
                int cut_v = -1;
                for (int j = 1; j < remain; j++) {
                    if (!ins[j]) {
                        w[j] += g[fa[j]][fa[u]];
                        if (w[j] > cut_v) {
                            cut_v = w[j];
                            v = j;
                        }
                    }
                }
                ins[v] = true;
            }
            ans = min(ans, w[v]);

            // 类似并查集的合并操作
            for (int i = 1; i < remain; i++) {
                if (i == v) continue;
                g[fa[i]][fa[0]] += g[fa[i]][fa[v]];
                g[fa[0]][fa[i]] += g[fa[v]][fa[i]];
            }
            remain--;
            fa[v] = fa[remain]; // 相当于是把 v 删掉了
        }

        write(ans);
        putchar('\n');
    }
}

Lutece 2710 是双倍经验。