最大流问题（Goldberg-Rao 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个非负容量 \( c(e) \geq 0 \)，以及源点 \( s \) 和汇点 \( t \)，求从 \( s \) 到 \( t \) 的最大流。Goldberg-Rao 算法是一种基于阻塞流（blocking flow）的高效算法，其时间复杂度为 \( O(\min\{V^{2/3}, E^{1/2}\} \cdot E \log(V^2/E) \log U) \)，其中 \( U \) 是最大边容量。该算法通过动态调整距离标签和容量缩放来优化性能，适用于大容量网络。 解题步骤 初始化 设流 \( f \) 初始为零流。 计算初始距离标签 \( d(v) \)（从 \( v \) 到 \( t \) 的BFS距离，在残量图中）。 设定初始缩放参数 \( \Delta \)（通常取 \( \Delta = \lfloor U/2 \rfloor \)，逐步缩小）。 迭代缩放阶段 当 \( \Delta \geq 1 \) 时重复以下步骤： 构建单位容量图 ：将残量图中容量 \( \geq \Delta \) 的边视为单位容量边，其余边容量视为0。 寻找阻塞流 ：在单位容量图中，使用最短路径（按距离标签 \( d \)）查找从 \( s \) 到 \( t \) 的阻塞流（即无法再通过最短路径增广的流）。 更新流 ：将阻塞流加入总流 \( f \)，更新残量图。 调整距离标签 ：若无法找到阻塞流，则更新距离标签 \( d(v) \)（通过BFS从 \( t \) 反向遍历残量图）。 缩小 \( \Delta \) ：当无法进一步增广时，设 \( \Delta \leftarrow \Delta/2 \)。 终止条件 当 \( \Delta < 1 \) 时，算法终止。此时流 \( f \) 即为最大流。 关键点说明 阻塞流 ：在单位容量图中，阻塞流的增广次数受 \( O(V^{2/3}) \) 或 \( O(E^{1/2}) \) 限制，这是算法高效的核心。 距离标签 ：通过维护 \( d(v) \)（到 \( t \) 的距离），确保每次增广沿最短路径进行，避免无效操作。 复杂度优势 ：结合容量缩放和单位容量图转化，算法在稀疏图或特定结构中优于传统 \( O(V^2E) \) 的算法。 通过以上步骤，Goldberg-Rao 算法以近似线性的复杂度（对于常见图）高效求解最大流问题。