最小割的等价边问题（Minimum Cut Minimum Cut Equivalent Edges） 题目描述 给定一个 无向连通加权图 \(G=(V,E,w)\)，其中每条边 \(e \in E\) 有一个正权值（容量）\(w(e)\)。图 \(G\) 的一个 最小割 是指一个边集 \(C \subseteq E\)，满足将 \(C\) 中的边删除后图不再连通，且 \(C\) 中所有边的权值之和最小。注意，一个图可能存在多个不同的最小割（即不同的边集，但权值和相同）。 本题要求：找出图中 所有这样的边 ，这些边出现在 至少一个最小割 中。我们称这些边为“最小割等价边”。你的任务是设计一个算法，在 多项式时间 内识别出所有最小割等价边。 问题输入 ：无向图 \(G\)，顶点数 \(n=|V|\)，边数 \(m=|E|\)，边权 \(w(e)>0\)。 问题输出 ：所有最小割等价边的列表。 解题思路 直接枚举所有最小割显然不可行（最小割数量可能指数级）。我们需借助 全局最小割的算法 （如 Stoer–Wagner 算法）以及最小割的若干性质。 关键观察： 设图的全局最小割的权值为 \(\lambda\)。 一条边 \(e=(u,v)\) 是最小割等价边，当且仅当存在 某个最小割 \(C\) 包含 \(e\)。 我们可以利用 边收缩 和 最小割的值 来判断一条边是否可能在某个最小割中。 以下是详细步骤： 第一步：复习全局最小割的定义与基本性质 一个割 \((S, V\setminus S)\) 对应的边集是 所有一端在 \(S\)、另一端在 \(V\setminus S\) 的边 ，割的权值是这些边的权值和。 全局最小割是权值最小的割（允许 \(S\) 或 \(V\setminus S\) 为空吗？不允许，因为割必须将图分成两个非空部分）。 设全局最小割的权值为 \(\lambda\)。 一个性质：如果我们将一条边 \(e\) 的权值增加一个很小的 \(\varepsilon>0\)，则新图的全局最小割权值要么不变，要么增加至多 \(\varepsilon\)，但若 \(e\) 包含在 所有 全局最小割中，则最小割权值必然增加（因为每个最小割都包含 \(e\)）。反之，如果 \(e\) 不在 任何 最小割中，则增加其权值不会影响最小割的权值。但这个性质不容易直接用来检测“出现在某个最小割中”。 第二步：利用“最小割等价边”的判定条件 一个重要结论（可由 Gomory–Hu 树或最大流最小割定理推导）： 固定一条边 \(e=(u,v)\)，考虑 以 \(\{u,v\}\) 为源汇的最小割 ，即计算 \(u\) 到 \(v\) 的最大流值（在无向图中，可将每条无向边替换为两条方向相反、容量相同的有向边，然后应用最大流算法）。设这个值为 \(f(u,v)\)。 如果 \(f(u,v) > \lambda\)，则存在一个 \(u\)-\(v\) 最小割的权值大于 \(\lambda\)，但全局最小割权值是 \(\lambda\)，所以 任何包含 \(e\) 的割 的权值至少是 \(f(u,v)\)（因为 \(u\)-\(v\) 最小割是将 \(u\) 和 \(v\) 分开的最小割，包含 \(e\) 意味着 \(u\) 和 \(v\) 必须位于割的两侧，因此这个割的权值至少是 \(f(u,v)\)）。 那么，如果 \(f(u,v) > \lambda\)，则包含 \(e\) 的割的权值严格大于 \(\lambda\)，因此 \(e\) 不可能在任何一个全局最小割中。 如果 \(f(u,v) = \lambda\)，则存在一个 \(u\)-\(v\) 最小割的权值等于 \(\lambda\)，这个割就是全局最小割，并且它包含 \(e\)（因为 \(u\) 和 \(v\) 在割的两侧，而 \(e\) 连接它们，所以 \(e\) 必然在这个割的边集中）。因此 \(e\) 出现在这个全局最小割中，所以 \(e\) 是等价边。 如果 \(f(u,v) < \lambda\)，这不可能，因为全局最小割的权值是 \(\lambda\)，而 \(f(u,v)\) 是某个割的权值，不可能比全局最小割还小。 因此，我们得到判定条件： 一条边 \(e=(u,v)\) 是最小割等价边，当且仅当 \(u\) 到 \(v\) 的最大流值（在无向图中）等于全局最小割的权值 \(\lambda\)。 第三步：算法框架 计算全局最小割的权值 \(\lambda\)（例如用 Stoer–Wagner 算法，时间复杂度 \(O(nm + n^2 \log n)\)）。 对每条边 \(e=(u,v)\)，计算 \(u\) 到 \(v\) 的最大流值 \(f(u,v)\)。 如果 \(f(u,v) = \lambda\)，则 \(e\) 是最小割等价边，否则不是。 但 ：上述步骤需要对每条边运行一次最大流，最坏要 \(m\) 次，每次最大流在无向图中用最高效的算法（如 Push–Relabel）是 \(O(n^3)\) 或 \(O(n^2 \sqrt{m})\)，总时间 \(O(m n^3)\) 太高。我们需要优化。 第四步：优化——利用 Gomory–Hu 树 Gomory–Hu 树是表示一个无向图所有顶点对间最小割的树结构，它有 \(n\) 个顶点、\(n-1\) 条树边，树边权值为对应顶点对在 原图 中的最小割权值。 关键性质： 对任意两顶点 \(s,t\)，它们在原图中的最小割权值等于它们在 Gomory–Hu 树路径上的最小边权。 构建 Gomory–Hu 树只需要 \(n-1\) 次最大流计算（而不是 \(m\) 次），经典算法复杂度 \(O(n \cdot \text{MaxFlow})\)，即 \(O(n \cdot (n^3))\) 或更好。 利用 Gomory–Hu 树，我们可以高效地得到任意两顶点间的最大流值（即最小割权值），而不需要对每条边都单独算一次最大流。 具体步骤： 构建原图 \(G\) 的 Gomory–Hu 树 \(T\)。 在树 \(T\) 上，对每条原图边 \(e=(u,v)\)，我们想知道 \(f(u,v)\)（即 \(u\) 到 \(v\) 在原图中的最小割权值）。根据 Gomory–Hu 树性质，\(f(u,v)\) 等于在树 \(T\) 中 \(u\) 到 \(v\) 的 路径上最小边权 。 我们可以在 \(O(n^2)\) 时间内预处理出树 \(T\) 上所有顶点对间路径的最小边权（用 DFS 或 LCA + RMQ 可做到 \(O(1)\) 查询）。 比较 \(f(u,v)\) 与 \(\lambda\)：若相等，则 \(e\) 是最小割等价边。 但注意 ：我们需要的是全局最小割权值 \(\lambda\)，而 Gomory–Hu 树的 最小边权 就是 \(\lambda\)（因为全局最小割对应树中权值最小的边）。 因此算法简化为： 构建 Gomory–Hu 树 \(T\)。 在 \(T\) 中找到权值最小的边，记其权值为 \(\lambda\)（即全局最小割权值）。 对原图 \(G\) 的每条边 \(e=(u,v)\)，计算树 \(T\) 中 \(u\) 到 \(v\) 路径上的最小边权 \(w_ {\min}(u,v)\)。 如果 \(w_ {\min}(u,v) = \lambda\)，则 \(e\) 是最小割等价边。 第五步：为什么这个条件正确？ 如果 \(w_ {\min}(u,v) = \lambda\)，说明在 \(T\) 中 \(u\) 到 \(v\) 的路径上有一条树边权值为 \(\lambda\)，这条树边对应原图的一个权值为 \(\lambda\) 的割，并且这个割将 \(u\) 和 \(v\) 分在两侧（由 Gomory–Hu 树性质保证），所以 \(e\) 必然穿过这个割，即在这个割的边集中。因此 \(e\) 出现在至少一个全局最小割中。 如果 \(w_ {\min}(u,v) > \lambda\)，则任何将 \(u\) 和 \(v\) 分开的割权值至少为 \(w_ {\min}(u,v) > \lambda\)，因此包含 \(e\) 的割权值大于 \(\lambda\)，不可能为全局最小割。所以 \(e\) 不是等价边。 第六步：算法步骤详述 构建 Gomory–Hu 树 输入无向图 \(G=(V,E,w)\)。 初始化 Gomory–Hu 树 \(T\) 为 \(n\) 个孤立顶点（与原图顶点相同）。 任选一个顶点作为根，用递归或迭代法：对当前树 \(T\) 的每个连通块（初始是整个顶点集），选取块中两个顶点 \(s,t\)，在原图（合并块中某些顶点后的图）上计算 \(s\) 到 \(t\) 的最大流，得到最小割 \((S,\bar{S})\) 和权值 \(f(s,t)\)。在 \(T\) 中连接 \(s\) 和 \(t\) 并赋予边权 \(f(s,t)\)。然后根据割将当前块分裂，递归处理。经典算法（Gusfield 1991）可在 \(n-1\) 次最大流内完成。 每次最大流可在无向图上用 Push–Relabel 实现，单次 \(O(n^3)\)，总 \(O(n^4)\)，但实践中用较好的最大流实现可更快。 找到全局最小割权值 \(\lambda\) Gomory–Hu 树 \(T\) 的 \(n-1\) 条边中，最小边权即为 \(\lambda\)。 预处理树 \(T\) 上任意两顶点间路径的最小边权 以树 \(T\) 的每个顶点为根，做 DFS 记录深度和父节点信息，用倍增法（Binary Lifting）预处理每个节点向上 \(2^k\) 步的祖先以及到该祖先路径上的最小边权。 这样，对任意两顶点 \(u,v\)，可在 \(O(\log n)\) 时间内查询 \(u\) 到 \(v\) 路径上的最小边权。 或者，因为 \(n\) 可能不大，也可用 \(O(n^2)\) 的 DP 直接算出所有顶点对的最小边权。 对原图每条边 \(e=(u,v)\) 判断 查询树 \(T\) 中 \(u\) 到 \(v\) 路径上的最小边权 \(w_ {\min}\)。 如果 \(w_ {\min} = \lambda\)，输出 \(e\) 为最小割等价边。 第七步：时间复杂度 构建 Gomory–Hu 树：\(n-1\) 次最大流，用 Push–Relabel 可做到 \(O(n^3)\) 每次，总 \(O(n^4)\)。实际有更优的实现可达 \(O(n^3 \sqrt{m})\) 等。 预处理树 \(T\) 的 LCA 与路径最小值：\(O(n \log n)\)。 对 \(m\) 条边查询：每次 \(O(\log n)\)，总 \(O(m \log n)\)。 总时间复杂度主要由 Gomory–Hu 树构建决定，是多项式时间。 第八步：举例说明 假设有一个简单无向图：4 个顶点 \(a,b,c,d\)，边权如下： \[ (a,b)=2,\ (b,c)=3,\ (c,d)=2,\ (d,a)=3,\ (a,c)=4,\ (b,d)=4 \] 构建 Gomory–Hu 树（过程略），得到树边及其权值：\((a,b):2,\ (b,c):3,\ (c,d):2\)。 最小边权 \(\lambda = 2\)（对应割 \(\{a,b\}\) 与 \(\{c,d\}\) 或 \(\{a,d\}\) 与 \(\{b,c\}\)）。 对原图每条边查询： 边 \((a,b)\)：在树中路径 \(a-b\) 的最小边权=2，等于 \(\lambda\)，所以是最小割等价边。 边 \((c,d)\)：同理，是最小割等价边。 边 \((b,c)\)：树路径 \(b-c\) 最小边权=2（路径 \(b-a-c\) 最小边权是 2），等于 \(\lambda\)，所以也是。 检查：实际上，最小割权值为 2 的割有哪些？例如割 \((\{a,b\},\{c,d\})\) 包含边 \((a,c),(a,d),(b,c),(b,d)\) 吗？不对，这个割只包含 \((a,c),(a,d),(b,c),(b,d)\) 四条边，它们的权值和是 4+3+3+4=14，显然不对。这里例子可能不太恰当，但说明了判定方法。 总结 本问题的核心是将“边是否在某个最小割中”转化为“该边两端点在 Gomory–Hu 树路径上的最小边权是否等于全局最小割权值”。利用 Gomory–Hu 树，我们只需 \(n-1\) 次最大流计算，即可高效回答所有边的查询，从而在多项式时间内找出所有最小割等价边。