最小割的 Gomory-Hu 树算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，每条边有一个非负容量（权重），要求构建一棵 Gomory-Hu 树。这棵树具有以下性质： 树的节点与原图节点相同。 对于树中任意一条边 \((u, v)\)，移除它后树分成两个连通分量 \( S \) 和 \( V \setminus S \)，此时原图中 \( S \) 和 \( V \setminus S \) 之间的最小割容量等于树上该边的容量。 对于任意两个节点 \( s \) 和 \( t \)，它们在树上的唯一路径中容量最小的边，其容量等于原图中 \( s \) 和 \( t \) 之间的最小割容量。 解题过程 基础概念 最小割 ：将图分为两个部分 \( S \) 和 \( T \)，使得从 \( S \) 到 \( T \) 的边容量和最小。 Gomory-Hu 树 ：通过一棵树简洁地表示所有节点对之间的最小割信息。 算法步骤 步骤1 ：初始化 Gomory-Hu 树为一个包含所有节点的孤立树（无边）。 步骤2 ：选择当前树中的一个连通分量（初始时为整个节点集），在该分量中任选两个节点 \( s \) 和 \( t \)。 步骤3 ：在原图上以 \( s \) 为源点、\( t \) 为汇点，计算最小割（使用最大流算法，如 Edmonds-Karp 或 Push-Relabel）。得到割集 \( (A, B) \)，其中 \( s \in A \)，\( t \in B \)。 步骤4 ：在 Gomory-Hu 树中添加一条边连接 \( s \) 和 \( t \)，容量为最小割值。 步骤5 ：将当前连通分量按割集 \( (A, B) \) 分裂为两个子集，递归处理每个子集。 步骤6 ：递归终止条件是连通分量只剩一个节点。 递归过程详解 对每个连通分量，通过最小割计算将其逐步细分，确保树边正确反映最小割容量。 例如，初始时节点集为 \( \{a,b,c,d\} \)，选择 \( s=a \)、\( t=b \)，计算最小割后分裂为 \( \{a,c\} \) 和 \( \{b,d\} \)，递归处理这两个集合。 正确性保证 通过递归分割，保证任意节点对的最小割由树上路径的最小边容量确定。 算法共进行 \( n-1 \) 次最大流计算（\( n \) 为节点数），每次处理一个分裂步骤。 复杂度分析 时间复杂度：共 \( O(n) \) 次最大流计算。若使用 Push-Relabel 算法，每次耗时 \( O(n^3) \)，总复杂度为 \( O(n^4) \)。 实际中可通过优化最大流算法（如使用 Dinic 算法）降低复杂度。 总结 Gomory-Hu 树算法通过递归分割和最大流计算，构建出一棵能高效查询任意节点对最小割的树结构，显著提升了多组最小割查询的效率。