OI-wiki 全局最小割完全指南Stoer–Wagner 算法原理、证明与模板实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文基于 OI-wiki 图论专题的 stoer-wagner.md 展开系统讲解在无向正权图上求解全局最小割无源汇最小割的 Stoer–Wagner 算法。你将掌握割在无源汇场景下的重定义、contract合并与最大权值点优先入集的核心操作、算法正确性的归纳证明以及一份可直接投入 OI / ICPC 竞赛的 C 模板实现含仓库测试数据验证并理解朴素实现与斐波那契堆优化版本的复杂度差异。从割说起为什么需要重新定义网络流中经典的最小割概念建立在源汇点之上将点集划分为 $S$ 与 $T V - S$要求源点 $s \in S$、汇点 $t \in T$割的容量为所有从 $S$ 到 $T$ 的边的容量之和最小割即取得该容量最小值的割详见 最小割。这种割常被称为${S-T}$ 割。而本文讨论的全局最小割问题取消了源汇点的定义需要对割这一概念做重定义。OI-wiki 原文特别指出网络流部分的割定义与维基百科不符只是由于一般接触到的割都是有源汇的最小割问题该概念才约定俗成。Stoer–Wagner 算法解决的正是去掉这一约束后的更一般情形。割在无向图 $G (V, E)$ 中设 $C$ 为图 $G$ 中一些弧的集合若从 $G$ 中删去 $C$ 中的所有弧能使图 $G$ 不是连通图则称 $C$ 为图 $G$ 的一个割。也就是说一个边集只要满足删掉它就能把图切成至少两个连通块就是图的一个割。这与网络流中点的划分表述不同但本质等价删除这些边后图被分成两个子图。有源汇点的最小割问题同 最小割 中的定义即经典的最大流 最小割问题。无源汇点的最小割问题包含的弧的权和最小的割也称为全局最小割Global Minimum Cut。全局最小割与有源汇最小割的区别在于它不关心把图切成哪两个部分只关心最少删掉多少权值的边能让图不连通。显然如果对每一对可能的源汇点都跑一遍网络流求最小割复杂度是行不通的——这正是 Stoer–Wagner 算法存在的意义。Stoer–Wagner 算法引入与性质Stoer–Wagner 算法由 Mechthild Stoer 与 Frank Wagner 于 1995 年提出是一种通过递归迭代收缩方式解决无向正权图上全局最小割问题的算法。算法复杂度为$$ O(|V||E| |V|^{2}\log|V|) $$一般可近似看作 $O(|V|^3)$。它的实现基于以下基本事实设图 $G$ 中有任意两点 $S, T$那么任意一个图 $G$ 的割 $C$或者有 $S, T$ 在同一连通块中或者$C$ 是一个 ${S-T}$ 割。这个事实把全局最小割的搜索空间分解为两类互斥情形$S, T$ 不在同一连通块此时割就是 ${S-T}$ 割问题退化为求一对指定点之间的最小割$S, T$ 在同一连通块此时可以把 $S, T$ 安全地合并成一点而不丢失最优解合并的正确性下文给出证明。算法过程三步循环收缩Stoer–Wagner 算法的主过程非常简洁在图 $G$ 中任意指定两点 $s, t$以这两点作为源汇点求出图 $G$ 的 ${S-T}$ 最小割定义为cut of phase即当前阶段的割并更新当前答案合并点 $s, t$。若图 $G$ 中 $|V|$ 仍大于 $1$则回到第一步输出所有cut of phase的最小值。合并contract操作的细节合并两点 $s, t$ 的具体操作是删除 $s, t$ 之间的连边 $(s, t)$对于 $G \setminus {s, t}$ 中任意一点 $k$删除 $(t, k)$并将其边权 $d(t, k)$加到$d(s, k)$ 上。正确性解释如果 $s, t$ 在同一连通块对于 $G \setminus {s, t}$ 中的一点 $k$假如 $(k, s) \in C_{\min}$即最优割包含边 $(k,s)$那么 $(k, t) \in C_{\min}$ 也一定成立——否则因为 $s, t$ 连通、$k, t$ 连通会导致 $s, k$ 仍处于同一连通块此时 $C C_{\min} \setminus {(t, k)}$ 将比 $C_{\min}$ 更优矛盾。反之亦然。所以 $s, t$ 可以看作同一点把 $t$ 的邻边全部吸收到 $s$ 上不会破坏任何全局最小割的结构。终止条件步骤 1 考虑了 $s, t$ 不在同一连通块的情形步骤 2 考虑了剩余的情形。由于每次执行步骤 2 都会使 $|V|$ 减小 $1$因此算法将在进行 $|V| - 1$ 轮后结束。S-T 最小割的求法最大权值点优先入集主过程的第一步要求以 $s, t$ 为源汇点求 ${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$即 $i$ 与集合 $A$ 中所有点的边权之和。容易知道所有点加入 $A$ 的顺序是固定的。令 $\operatorname{ord}(i)$ 表示第 $i$ 个加入 $A$ 的点$t \operatorname{ord}(|V|)$即最后一个加入 $A$ 的点$\operatorname{pos}(v)$ 表示 $v$ 被加入 $A$ 后 $|A|$ 的大小即 $v$ 被加入的顺序。则对任意点 $s$倒数第二个加入 $A$ 的点一个 $s$ 到 $t$ 的割即为 $w(t)$——也就是说最后加入集合 $A$ 的点 $t$ 与集合 $A$ 的连边权和 $w(A_t, t) w(t)$恰好就是当前阶段的最小 ${S-T}$ 割容量即cut of phase。正确性证明激活点与 Lemma 1这一构造看似神奇其正确性由激活点activated vertex概念与一条关键引理保证。激活点的定义定义一个点 $v$被激活当且仅当$v$ 在加入 $A$ 时发现在 $A$ 中此时最后一个点 $u$ 早于 $v$ 加入集合并且在图 $G (V, E / C)$ 中$C$ 为某个割$E/C$ 表示删去 $C$ 中的边后剩余的图$u$ 与 $v$ 不在同一连通块。如图原图蓝色区域和黄色区域为两个不同的连通块方括号中的数字为加入 $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})$因为此时 $A_{v_0}$ 中的点与 $v_0$ 之间所有边都必然跨越割 $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)$因为 $u$ 是被贪心选出的最大权值点$u$ 加入时它到 $A_v$ 的边权和不可能超过 $v$ 加入时的 $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)$即 $u$ 与晚于 $v$ 加入的点的连边权对 $w(C_u)$ 有贡献而对 $w(C_v)$ 没有贡献在所有边均为正权的情况下可导出$$ w(A_u, u) \le w(C_u) $$由归纳法得证。最后由于 $\operatorname{pos}(s) \operatorname{pos}(t)$$s$ 早于 $t$ 入集并且 $s, t$ 不在同一连通块因此 $t$ 会被激活由此得出$$ w(A_t, t) \le w(C_t) w(C) $$而 $w(A_t, t)$ 本身是 $s$ 到 $t$ 的一个割的容量故它正是当前阶段的最小割 $w(t)$引理保证了 $s$ 到 $t$ 的任何割 $C$ 的容量都不小于它从而确认了最后一个入集的点 $t$ 的权值 $w(t)$ 就是该阶段最小割这一结论。注意所有边均为正权是证明的关键前提这正是算法只适用于无向正权图的原因。模板实现源码逐段解析原文档给出的是 Luogu P5632【模板】Stoer–Wagner 算法的参考代码完整实现在 stoer-wagner_1.cpp。下面逐段解读其关键结构。#include cstring #include iostream using namespace std; constexpr 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;N 601题目数据规模的容量上限邻接矩阵存边注意无向图需双向加权fa / siz / find并查集用于预判图是否连通若原图不连通全局最小割显然为 $0$dist[j]即权值函数 $w(A, j)$当前与集合 $A$ 的连边权和vis[j]本轮 contract 中是否已加入集合 $A$bin[j]该点是否已被合并退出后续阶段。contract 函数一次阶段最小割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; }这段代码完整实现了S-T 最小割的求法每轮循环从未入集且未合并的点中暴力扫描出dist[j]最大的点 $k$对应权值函数 $w(A, i)$ 最大s t; t k;维护加入顺序mincut maxc记录 $w(t)$将 $k$ 标记入集vis[k] true并把 $k$ 到所有未入集点的边权累加到对应的dist[j]上即完成 $w(A \cup {k}, \cdot)$ 的增量更新。注意if (k -1) return mincut;处理了某些边界情形例如全部剩余点都已合并。Stoer_Wagner 主循环与合并constexpr 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; }外层循环恰好执行 $n - 1 |V| - 1$ 次对应每次合并使 $|V|$ 减 $1$的终止条件每次contract后取出阶段最小割ans更新全局答案bin[t] true表示点 $t$ 已被合并合并操作edge[s][j] (edge[j][s] edge[j][t])即把 $t$ 的边权加到 $s$ 上对称更新符合无向图存储与文档中删除 $(t,k)$ 并把 $d(t,k)$ 加到 $d(s,k)$的表述完全一致一旦发现最小割为 $0$ 可提前返回图已被切空不可能更小。main 函数连通性预处理int main() { ios::sync_with_stdio(false), cin.tie(nullptr); 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; }两个重要的边界处理m n - 1边数不足以让图连通最小割直接为 $0$读入时用**按大小合并union by size**的并查集维护连通性最后检查siz[find(1)] ! n——若整个图不连通全局最小割为 $0$无需再跑算法。此外读入使用edge[u][v] w的累加写法可正确处理重边多条边合并为一条。用仓库测试数据验证仓库中随附了该模板的测试数据输入 stoer-wagner_1.in4 6 1 2 5 1 3 1 2 4 1 3 4 2 2 3 1 1 4 2期望输出 stoer-wagner_1.ans4这是一个 4 点 6 边的无向正权图。直观验证删掉边 $(1,3)$权 1、$(2,3)$权 1、$(3,4)$权 2可以将点 3 单独切出总权值为 $1124$任何其他切法如沿 $(1,2)$ 权 5 或 $(1,4)$ 权 2 的组合都不小于 4故全局最小割为 4与算法输出一致。将输入数据编译运行 stoer-wagner_1.cpp 即可复现该结果。复杂度分析与优化方向一次contract阶段操作的复杂度为 $O(|E| |V|\log|V|)$一共进行 $O(|V|)$ 次contract因此总复杂度为 $O(|E||V| |V|^2\log|V|)$上述朴素实现中找最大权值点采用 $O(|V|)$ 暴力扫描实际是 $O(|V|^3)$ 量级与原文档给出的复杂度公式一致。根据 最短路 的经验算法瓶颈在于找到权值最大的点在一次contract中需要找 $|V|$ 次堆顶并递增地修改 $|E|$ 次权值每次加入新点后对未入集点做dist[j] edge[k][j]斐波那契堆可以胜任 $O(\log|V|)$ 查找堆顶和 $O(1)$ 递增修改权值的工作理论复杂度可以达到 $O(|E| |V|\log|V|)$。然而OI-wiki 原文也给出了工程上的冷静判断由于斐波那契堆常数过大、码量高实际应用价值偏低——实际测试中即使开 O2 优化也需要卡评测波动才能通过。因此在竞赛实践中朴素的 $O(|V|^3)$ 实现即仓库中的模板写法往往是更务实的选择。小结Stoer–Wagner 算法以任意两点要么被割开、要么可安全合并为基石通过 $|V| - 1$ 轮最大权值点贪心入集 合并操作在 $O(|V|^3)$ 的朴素实现下即可求解无向正权图的全局最小割且与网络流解法相比完全不需要指定源汇点。其正确性由激活点与 Lemma 1 的归纳证明严格保证配合并查集连通性预判、重边累加等实现细节即可得到一份稳健的竞赛模板。核心代码与测试数据可分别在 模板实现 与 测试样例 中直接查阅和复现。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
OI-wiki 全局最小割完全指南：Stoer–Wagner 算法原理、证明与模板实现
OI-wiki 全局最小割完全指南Stoer–Wagner 算法原理、证明与模板实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文基于 OI-wiki 图论专题的 stoer-wagner.md 展开系统讲解在无向正权图上求解全局最小割无源汇最小割的 Stoer–Wagner 算法。你将掌握割在无源汇场景下的重定义、contract合并与最大权值点优先入集的核心操作、算法正确性的归纳证明以及一份可直接投入 OI / ICPC 竞赛的 C 模板实现含仓库测试数据验证并理解朴素实现与斐波那契堆优化版本的复杂度差异。从割说起为什么需要重新定义网络流中经典的最小割概念建立在源汇点之上将点集划分为 $S$ 与 $T V - S$要求源点 $s \in S$、汇点 $t \in T$割的容量为所有从 $S$ 到 $T$ 的边的容量之和最小割即取得该容量最小值的割详见 最小割。这种割常被称为${S-T}$ 割。而本文讨论的全局最小割问题取消了源汇点的定义需要对割这一概念做重定义。OI-wiki 原文特别指出网络流部分的割定义与维基百科不符只是由于一般接触到的割都是有源汇的最小割问题该概念才约定俗成。Stoer–Wagner 算法解决的正是去掉这一约束后的更一般情形。割在无向图 $G (V, E)$ 中设 $C$ 为图 $G$ 中一些弧的集合若从 $G$ 中删去 $C$ 中的所有弧能使图 $G$ 不是连通图则称 $C$ 为图 $G$ 的一个割。也就是说一个边集只要满足删掉它就能把图切成至少两个连通块就是图的一个割。这与网络流中点的划分表述不同但本质等价删除这些边后图被分成两个子图。有源汇点的最小割问题同 最小割 中的定义即经典的最大流 最小割问题。无源汇点的最小割问题包含的弧的权和最小的割也称为全局最小割Global Minimum Cut。全局最小割与有源汇最小割的区别在于它不关心把图切成哪两个部分只关心最少删掉多少权值的边能让图不连通。显然如果对每一对可能的源汇点都跑一遍网络流求最小割复杂度是行不通的——这正是 Stoer–Wagner 算法存在的意义。Stoer–Wagner 算法引入与性质Stoer–Wagner 算法由 Mechthild Stoer 与 Frank Wagner 于 1995 年提出是一种通过递归迭代收缩方式解决无向正权图上全局最小割问题的算法。算法复杂度为$$ O(|V||E| |V|^{2}\log|V|) $$一般可近似看作 $O(|V|^3)$。它的实现基于以下基本事实设图 $G$ 中有任意两点 $S, T$那么任意一个图 $G$ 的割 $C$或者有 $S, T$ 在同一连通块中或者$C$ 是一个 ${S-T}$ 割。这个事实把全局最小割的搜索空间分解为两类互斥情形$S, T$ 不在同一连通块此时割就是 ${S-T}$ 割问题退化为求一对指定点之间的最小割$S, T$ 在同一连通块此时可以把 $S, T$ 安全地合并成一点而不丢失最优解合并的正确性下文给出证明。算法过程三步循环收缩Stoer–Wagner 算法的主过程非常简洁在图 $G$ 中任意指定两点 $s, t$以这两点作为源汇点求出图 $G$ 的 ${S-T}$ 最小割定义为cut of phase即当前阶段的割并更新当前答案合并点 $s, t$。若图 $G$ 中 $|V|$ 仍大于 $1$则回到第一步输出所有cut of phase的最小值。合并contract操作的细节合并两点 $s, t$ 的具体操作是删除 $s, t$ 之间的连边 $(s, t)$对于 $G \setminus {s, t}$ 中任意一点 $k$删除 $(t, k)$并将其边权 $d(t, k)$加到$d(s, k)$ 上。正确性解释如果 $s, t$ 在同一连通块对于 $G \setminus {s, t}$ 中的一点 $k$假如 $(k, s) \in C_{\min}$即最优割包含边 $(k,s)$那么 $(k, t) \in C_{\min}$ 也一定成立——否则因为 $s, t$ 连通、$k, t$ 连通会导致 $s, k$ 仍处于同一连通块此时 $C C_{\min} \setminus {(t, k)}$ 将比 $C_{\min}$ 更优矛盾。反之亦然。所以 $s, t$ 可以看作同一点把 $t$ 的邻边全部吸收到 $s$ 上不会破坏任何全局最小割的结构。终止条件步骤 1 考虑了 $s, t$ 不在同一连通块的情形步骤 2 考虑了剩余的情形。由于每次执行步骤 2 都会使 $|V|$ 减小 $1$因此算法将在进行 $|V| - 1$ 轮后结束。S-T 最小割的求法最大权值点优先入集主过程的第一步要求以 $s, t$ 为源汇点求 ${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$即 $i$ 与集合 $A$ 中所有点的边权之和。容易知道所有点加入 $A$ 的顺序是固定的。令 $\operatorname{ord}(i)$ 表示第 $i$ 个加入 $A$ 的点$t \operatorname{ord}(|V|)$即最后一个加入 $A$ 的点$\operatorname{pos}(v)$ 表示 $v$ 被加入 $A$ 后 $|A|$ 的大小即 $v$ 被加入的顺序。则对任意点 $s$倒数第二个加入 $A$ 的点一个 $s$ 到 $t$ 的割即为 $w(t)$——也就是说最后加入集合 $A$ 的点 $t$ 与集合 $A$ 的连边权和 $w(A_t, t) w(t)$恰好就是当前阶段的最小 ${S-T}$ 割容量即cut of phase。正确性证明激活点与 Lemma 1这一构造看似神奇其正确性由激活点activated vertex概念与一条关键引理保证。激活点的定义定义一个点 $v$被激活当且仅当$v$ 在加入 $A$ 时发现在 $A$ 中此时最后一个点 $u$ 早于 $v$ 加入集合并且在图 $G (V, E / C)$ 中$C$ 为某个割$E/C$ 表示删去 $C$ 中的边后剩余的图$u$ 与 $v$ 不在同一连通块。如图原图蓝色区域和黄色区域为两个不同的连通块方括号中的数字为加入 $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})$因为此时 $A_{v_0}$ 中的点与 $v_0$ 之间所有边都必然跨越割 $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)$因为 $u$ 是被贪心选出的最大权值点$u$ 加入时它到 $A_v$ 的边权和不可能超过 $v$ 加入时的 $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)$即 $u$ 与晚于 $v$ 加入的点的连边权对 $w(C_u)$ 有贡献而对 $w(C_v)$ 没有贡献在所有边均为正权的情况下可导出$$ w(A_u, u) \le w(C_u) $$由归纳法得证。最后由于 $\operatorname{pos}(s) \operatorname{pos}(t)$$s$ 早于 $t$ 入集并且 $s, t$ 不在同一连通块因此 $t$ 会被激活由此得出$$ w(A_t, t) \le w(C_t) w(C) $$而 $w(A_t, t)$ 本身是 $s$ 到 $t$ 的一个割的容量故它正是当前阶段的最小割 $w(t)$引理保证了 $s$ 到 $t$ 的任何割 $C$ 的容量都不小于它从而确认了最后一个入集的点 $t$ 的权值 $w(t)$ 就是该阶段最小割这一结论。注意所有边均为正权是证明的关键前提这正是算法只适用于无向正权图的原因。模板实现源码逐段解析原文档给出的是 Luogu P5632【模板】Stoer–Wagner 算法的参考代码完整实现在 stoer-wagner_1.cpp。下面逐段解读其关键结构。#include cstring #include iostream using namespace std; constexpr 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;N 601题目数据规模的容量上限邻接矩阵存边注意无向图需双向加权fa / siz / find并查集用于预判图是否连通若原图不连通全局最小割显然为 $0$dist[j]即权值函数 $w(A, j)$当前与集合 $A$ 的连边权和vis[j]本轮 contract 中是否已加入集合 $A$bin[j]该点是否已被合并退出后续阶段。contract 函数一次阶段最小割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; }这段代码完整实现了S-T 最小割的求法每轮循环从未入集且未合并的点中暴力扫描出dist[j]最大的点 $k$对应权值函数 $w(A, i)$ 最大s t; t k;维护加入顺序mincut maxc记录 $w(t)$将 $k$ 标记入集vis[k] true并把 $k$ 到所有未入集点的边权累加到对应的dist[j]上即完成 $w(A \cup {k}, \cdot)$ 的增量更新。注意if (k -1) return mincut;处理了某些边界情形例如全部剩余点都已合并。Stoer_Wagner 主循环与合并constexpr 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; }外层循环恰好执行 $n - 1 |V| - 1$ 次对应每次合并使 $|V|$ 减 $1$的终止条件每次contract后取出阶段最小割ans更新全局答案bin[t] true表示点 $t$ 已被合并合并操作edge[s][j] (edge[j][s] edge[j][t])即把 $t$ 的边权加到 $s$ 上对称更新符合无向图存储与文档中删除 $(t,k)$ 并把 $d(t,k)$ 加到 $d(s,k)$的表述完全一致一旦发现最小割为 $0$ 可提前返回图已被切空不可能更小。main 函数连通性预处理int main() { ios::sync_with_stdio(false), cin.tie(nullptr); 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; }两个重要的边界处理m n - 1边数不足以让图连通最小割直接为 $0$读入时用**按大小合并union by size**的并查集维护连通性最后检查siz[find(1)] ! n——若整个图不连通全局最小割为 $0$无需再跑算法。此外读入使用edge[u][v] w的累加写法可正确处理重边多条边合并为一条。用仓库测试数据验证仓库中随附了该模板的测试数据输入 stoer-wagner_1.in4 6 1 2 5 1 3 1 2 4 1 3 4 2 2 3 1 1 4 2期望输出 stoer-wagner_1.ans4这是一个 4 点 6 边的无向正权图。直观验证删掉边 $(1,3)$权 1、$(2,3)$权 1、$(3,4)$权 2可以将点 3 单独切出总权值为 $1124$任何其他切法如沿 $(1,2)$ 权 5 或 $(1,4)$ 权 2 的组合都不小于 4故全局最小割为 4与算法输出一致。将输入数据编译运行 stoer-wagner_1.cpp 即可复现该结果。复杂度分析与优化方向一次contract阶段操作的复杂度为 $O(|E| |V|\log|V|)$一共进行 $O(|V|)$ 次contract因此总复杂度为 $O(|E||V| |V|^2\log|V|)$上述朴素实现中找最大权值点采用 $O(|V|)$ 暴力扫描实际是 $O(|V|^3)$ 量级与原文档给出的复杂度公式一致。根据 最短路 的经验算法瓶颈在于找到权值最大的点在一次contract中需要找 $|V|$ 次堆顶并递增地修改 $|E|$ 次权值每次加入新点后对未入集点做dist[j] edge[k][j]斐波那契堆可以胜任 $O(\log|V|)$ 查找堆顶和 $O(1)$ 递增修改权值的工作理论复杂度可以达到 $O(|E| |V|\log|V|)$。然而OI-wiki 原文也给出了工程上的冷静判断由于斐波那契堆常数过大、码量高实际应用价值偏低——实际测试中即使开 O2 优化也需要卡评测波动才能通过。因此在竞赛实践中朴素的 $O(|V|^3)$ 实现即仓库中的模板写法往往是更务实的选择。小结Stoer–Wagner 算法以任意两点要么被割开、要么可安全合并为基石通过 $|V| - 1$ 轮最大权值点贪心入集 合并操作在 $O(|V|^3)$ 的朴素实现下即可求解无向正权图的全局最小割且与网络流解法相比完全不需要指定源汇点。其正确性由激活点与 Lemma 1 的归纳证明严格保证配合并查集连通性预判、重边累加等实现细节即可得到一份稳健的竞赛模板。核心代码与测试数据可分别在 模板实现 与 测试样例 中直接查阅和复现。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
