xxx 最小割的 Gomory-Hu 树算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，每条边有一个非负容量（权重）。Gomory-Hu 树（又称割树）是一种数据结构，它能高效地表示图中所有顶点对之间的最小割值。具体来说，Gomory-Hu 树是一棵带权树 \( T = (V, E_ T) \)，使得对于任意两个顶点 \( s \) 和 \( t \)，\( T \) 中 \( s \) 到 \( t \) 路径上的最小边权等于原图中 \( s \) 和 \( t \) 之间的最小割容量。要求构造这样的树。 解题过程 1. 理解最小割与 Gomory-Hu 树的作用 图中两个顶点 \( s \) 和 \( t \) 的最小割是指删除一组边后使 \( s \) 和 \( t \) 不连通，且删除边的总容量最小。 Gomory-Hu 树将原图的所有最小割信息压缩到一棵树中，树中任意两点路径的最小边权就是原图对应两点的最小割值。 例如，若树中 \( s \) 到 \( t \) 的路径上最小边权为 5，则原图中分离 \( s \) 和 \( t \) 的最小割容量为 5。 2. 算法核心思想：递归分割与收缩操作 Gomory-Hu 算法采用分治策略，逐步构建树结构。 关键步骤： a. 选择当前顶点集的一个划分（两个非空子集 \( A \) 和 \( B \)）。 b. 在原图中计算 \( A \) 和 \( B \) 之间的最小割（通过添加超级源/汇点）。 c. 根据最小割将图分割成两部分，递归处理每部分，同时将另一部分收缩为一个顶点（保留所有边容量之和）。 最终，所有递归步骤的割信息合并成一棵树。 3. 具体步骤（Gomory-Hu 算法） 步骤 1：初始化 设当前顶点集为 \( S = V \)，初始树 \( T \) 为空。 选择一个顶点 \( r \) 作为根（如 \( r = v_ 1 \)），并维护一个顶点集合 \( U = V \setminus \{r\} \)。 步骤 2：递归构建树 对于每个顶点 \( u \in U \)： a. 在当前图 \( G \) 中，以 \( r \) 为源点，\( u \) 为汇点，计算最小割（使用最大流算法，如 Edmonds-Karp 或 Push-Relabel）。 b. 设最小割将顶点集分为 \( X \)（含 \( r \)）和 \( Y \)（含 \( u \)）。 c. 在树 \( T \) 中添加边 \( (r, u) \)，权重为最小割值。 d. 收缩 \( Y \) 为一个新顶点 \( y' \)，更新图 \( G \)：保留 \( X \) 和 \( y' \) 之间的边，容量为原图中 \( X \) 到 \( Y \) 的总容量。 e. 递归处理 \( Y \) 中的顶点（将 \( y' \) 视为新的根，更新 \( U \) 为 \( Y \) 中的顶点）。 步骤 3：合并子树 递归结束后，所有边被添加到树 \( T \) 中，形成 Gomory-Hu 树。 4. 实例演示（简单图） 考虑图 \( G \) 有顶点 \( \{a, b, c\} \)，边容量：\( (a,b)=3, (a,c)=5, (b,c)=2 \)。 选根 \( r = a \)，\( U = \{b, c\} \)。 对 \( u = b \)：计算 \( a \) 和 \( b \) 的最小割（割值为 3），割分 \( X=\{a,c\}, Y=\{b\} \)。添加树边 \( (a,b) \) 权重 3。收缩 \( Y \) 后递归结束（因 \( Y \) 只剩一个顶点）。 对 \( u = c \)：在收缩 \( b \) 后的图中计算 \( a \) 和 \( c \) 的最小割（割值为 5），添加树边 \( (a,c) \) 权重 5。 最终树为 \( a-b(3), a-c(5) \)。验证：\( b \) 和 \( c \) 的最小割为路径 \( b-a-c \) 的最小边权 3（原图中 \( b,c \) 最小割确实为 3）。 5. 复杂度与注意事项 需执行 \( |V|-1 \) 次最大流计算，每次流算法复杂度取决于实现（如 \( O(|V|^3) \)）。 收缩操作需谨慎处理边容量累加，避免重复计算。 树中路径的最小边权可直接用树上查询（如倍增法）快速得到。 通过以上步骤，Gomory-Hu 树将原图的最小割问题转化为树上的简单查询，极大提升了多组最小割计算的效率。