图论中的最小割树（Gomory-Hu Tree）算法 题目描述 最小割树（Gomory-Hu Tree）是一种高效表示图中所有顶点对之间最小割的结构。给定一个无向连通图 \( G = (V, E) \) 和边容量函数 \( c: E \to \mathbb{R}^+ \)，Gomory-Hu Tree 是一棵树 \( T = (V, E_ T) \)，使得对于任意两个顶点 \( s, t \in V \)，\( T \) 中连接 \( s \) 和 \( t \) 的路径上的最小边权值等于 \( G \) 中 \( s \) 和 \( t \) 之间的最小割容量。该算法通过递归分割顶点集并计算最小割来构建这棵树。 解题步骤 初始化 设当前顶点集为 \( S = V \)，初始树 \( T \) 为空。 选择一个顶点 \( s \in S \) 作为当前集合的“代表点”。 递归分割过程 若 \( |S| = 1 \)，直接返回（无需进一步分割）。 否则，从 \( S \) 中任选一个不同于 \( s \) 的顶点 \( t \)。 在原始图 \( G \) 上计算 \( s \) 和 \( t \) 之间的最小割（例如使用 Stoer-Wagner 算法或最大流算法）。设最小割将 \( V \) 分成两个集合 \( A \) 和 \( B \)，其中 \( s \in A \)，\( t \in B \)。 记录割容量 \( \lambda(s, t) \) 作为树 \( T \) 中边 \( (s, t) \) 的权值。 构建子树 将图 \( G \) 根据割 \( (A, B) \) 分割成两个子图 \( G_ A \) 和 \( G_ B \)，其中 \( G_ A \) 包含 \( A \) 中的顶点及它们之间的边，\( G_ B \) 同理。 递归地对 \( G_ A \) 和 \( G_ B \) 应用相同过程，分别以 \( s \) 和 \( t \) 作为代表点。 在递归过程中，将子树通过边 \( (s, t) \) 连接，权值为 \( \lambda(s, t) \)。 终止条件 当每个顶点集大小为 1 时，递归终止。此时树 \( T \) 包含所有顶点，且任意两顶点路径上的最小边权对应其最小割容量。 示例说明 假设图 \( G \) 有顶点集 \( \{a, b, c, d\} \)，边容量如图所示。 第一步：选 \( s = a \)，\( t = b \)，计算最小割容量为 3，分割成 \( A = \{a, d\} \) 和 \( B = \{b, c\} \)。 递归处理 \( A \)：在子图 \( G_ A \) 中计算 \( a \) 和 \( d \) 的最小割（容量为 5），添加边 \( (a, d) \) 到树。 递归处理 \( B \)：在子图 \( G_ B \) 中计算 \( b \) 和 \( c \) 的最小割（容量为 4），添加边 \( (b, c) \) 到树。 最终树结构为 \( a-d \)（权 5）、\( a-b \)（权 3）、\( b-c \)（权 4）。验证任意顶点对（如 \( c \) 和 \( d \)）的最小割为路径 \( c-b-a-d \) 上的最小边权 \( \min(4, 3, 5) = 3 \)。 关键点 算法通过 \( |V| - 1 \) 次最小割计算构建树，优于直接计算所有顶点对的最小割（\( O(|V|^2) \) 次）。 树结构支持快速查询任意两点最小割，仅需一次路径搜索。 实际实现中需注意缩点操作：在递归子图中，将已分割的集合缩成一个顶点以保持连通性。