xxx 最小割的 Gomory-Hu 树算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，每条边有一个正整数权重（容量），要求高效地计算图中所有顶点对之间的最小割值。具体来说，对于任意两个顶点 \( s \) 和 \( t \)，需要快速得到 \( s-t \) 最小割的容量。直接对每个顶点对运行最大流算法（如 Dinic 算法）的时间复杂度较高（共需 \( O(|V|^2) \) 次最大流计算）。Gomory-Hu 树算法通过构建一棵树（称为 Gomory-Hu 树），使得任意两点在树上的唯一路径中，最小权重的边恰好对应原图中这两点间的最小割容量，从而将问题转化为一次树上的查询。 解题过程 基本思想 Gomory-Hu 树是一棵带权树 \( T = (V, E_ T) \)，满足以下性质： 对任意两点 \( s, t \in V \)，在 \( T \) 中唯一路径上的最小边权重等于原图中 \( s-t \) 最小割的容量。 移除这条最小边后，树分裂成的两个连通分量恰好构成原图的一个 \( s-t \) 最小割。 算法通过递归划分顶点集，逐步构建这棵树。 算法步骤 初始化 ：从任意顶点集合开始（初始为整个顶点集 \( V \)），构建一棵初始树（可简化为单个节点，逐步扩展）。 递归划分 ： 在当前顶点集合 \( S \subseteq V \) 中任选两个顶点 \( u, v \)（若 \( |S| = 1 \) 则跳过）。 计算 \( u-v \) 最小割：将原图收缩（合并）当前树中其他连通分量（除 \( S \) 外的部分），得到一个新图 \( G' \)，在 \( G' \) 上运行最大流算法（如 Edmonds-Karp 或 Dinic）求 \( u-v \) 最小割的容量 \( \lambda \) 和割集 \( (A, B) \)，其中 \( u \in A, v \in B \)。 添加树边 ：在树中添加一条连接 \( u \) 和 \( v \) 的边，权重为 \( \lambda \)。 分裂集合 ：将 \( S \) 划分为 \( A \cap S \) 和 \( B \cap S \)，递归处理这两个子集。 终止条件 ：当每个顶点集合的大小为 1 时停止递归。 实例演示 考虑一个简单图：顶点集 \( V = \{1,2,3\} \)，边 \( (1,2) \) 容量 2，\( (2,3) \) 容量 3，\( (1,3) \) 容量 3。 初始集合 \( S = \{1,2,3\} \)，选 \( u=1, v=2 \)。计算最小割：割集 \( A=\{1\}, B=\{2,3\} \)，容量 \( \lambda=2 \)。添加树边 \( (1,2) \) 权重 2。 分裂 \( S \)：子集 \( S_ 1 = \{1\} \)（终止），子集 \( S_ 2 = \{2,3\} \)。 在 \( S_ 2 \) 中选 \( u=2, v=3 \)。计算最小割：割集 \( A=\{2\}, B=\{3\} \)，容量 \( \lambda=3 \)。添加树边 \( (2,3) \) 权重 3。 最终 Gomory-Hu 树为边集 \( \{(1,2,2), (2,3,3)\} \)。 验证：点 1 和 3 的路径上最小边权重为 \( \min(2,3)=2 \)，原图中 1-3 最小割容量确实为 2（割集 \( \{1\}, \{2,3\} \)）。 复杂度分析 共需 \( |V|-1 \) 次最大流计算（每次递归减少一个集合）。 若使用 Dinic 算法（复杂度 \( O(|V|^2|E|) \)），总复杂度为 \( O(|V|^3|E|) \)，但实际中通过优化（如使用当前树结构避免重复计算）可提升效率。 应用场景 网络可靠性分析：快速评估任意两点间的连通性。 图像分割：将图像像素视为顶点，边权重表示相似度，通过最小割划分区域。 动态最小割查询：一旦构建 Gomory-Hu 树，每次查询仅需 \( O(|V|) \) 时间。