-
YAML 元数据 已设置 tags: [KACTL, 图论, 核心概念]。
-
核心概述 以 N−1 次 s–t 最小割构造一棵树，使任意两点最小割等于该树上路径最小边权；适合批量最小割查询的离线预处理。
-
原文引述
Description: Build a Gomory–Hu tree of an undirected weighted graph so that the min s–t cut for any pair (s,t) equals the minimum edge weight on the unique path between s and t in the tree. Time: O(N · T_cut)
- 展开阐述
-
定义与背景
- 目标：在无向非负权图上，构造 GH 树 T（一棵包含原图所有点的树），使得任意 u,v 的最小割值等于 T 上 u→v 唯一路径的最小边权。
- 适用场景：需要处理大量“任意两点最小割”查询时，将代价从多次最小割降为“树上最小边权”查询（可用倍增/LCA 预处理）。
-
接口/数据结构（据实现习惯）
- gomoryHu(G)：输入无向带权图，返回 parent 数组与边权 w，其中边 (i, parent[i]) 的权 w[i] 即为 mincut(i, parent[i])。
- 输入约束：自环忽略，多边按权累加（或取和/最小，依实现）；要求 w[u][v]=w[v][u]，边权非负。
-
核心流程/要点（N−1 次 s–t 最小割 + 父指针重定向）
- 初始化：par[i]=0（i>0），w[i] 未定。
- 对 i=1..N−1：
- 计算 cut(i, par[i]) 得到割值 w[i] 与割一侧集合 S；
- 对所有 j≠i 且 par[j]==par[i] 且 j∈S：将 par[j] 置为 i（把与 i 同侧的点挂到 i）；
- 若 par[par[i]] ∈ S：交换 i 与 par[i] 的父子关系以维持树的结构一致性。
- 输出边集 {(i, par[i], w[i]) | i=1..N−1} 即 GH 树。
-
复杂度与边界条件
- 总复杂度：O(N · T_cut)，其中 T_cut 为一次 s–t 最小割/最大流时间（可选 057-图论-Dinic最大流、060-图论-EdmondsKarp、076-图论-PushRelabel 实作）。
- 图连通性：若图不连通，跨分量的最小割为 0；树上对应路径最小边权也为 0（通过与根的 0 边逐层连接）。
- 精度与权值：权值需非负；大权值或浮点时注意比较与累计的数值稳定性。
- 结构正确性：每次更新 par 的重定向只在同一割侧进行，保证最终是一棵树且能保持割值不变性。
-
变体/扩展与关系
- 查询加速：在 GH 树上预处理 LCA 与路径最小边权（如倍增维护），可 O(log N) 回答任意最小割查询。
- 与全局最小割：全局最小割等于 GH 树中最小边权（见 064-图论-全局最小割），但 GH 提供任意点对的完整刻画。
- 与最大流族：GH 仅调用 N−1 次 s–t 最小割；当需要多对查询时，整体成本通常低于对每对都独立跑一次最小割。
-
正确性要点与不变式
- 不变式：对任意已处理的顶点集合，树中边权等于相应 s–t 最小割；父指针重定向只在割的一侧进行，不改变其他点对的最小割值。
- 结论：由 Gomory–Hu 定理，所得树满足 mincut(u,v) 等于该树路径上的最小边权，进而实现任意点对最小割的等价查询。
-
与相邻技术的取舍建议
- 若只需单个 s–t 最小割，直接用最大流；
- 若需全局最小割值，用 Stoer–Wagner 更简洁；
- 若需多对最小割查询或全域刻画，优先构造 GH 树。
- 关联节点