xxx 最大流问题（Goldberg-Rao 算法）

题目描述
Goldberg-Rao 算法是一种用于求解有向图最大流问题的高效算法。给定一个有向图，其中每条边有一个非负容量，以及源点 \(s\) 和汇点 \(t\)，目标是找到从 \(s\) 到 \(t\) 的最大流量。该算法通过结合容量缩放和最短路径距离，在 \(O(\min\{n^{2/3}, m^{1/2}\} \cdot m \log(n^2/m) \log U)\) 的时间内解决问题，其中 \(n\) 是顶点数，\(m\) 是边数，\(U\) 是最大边容量。

解题过程

1. 初始化

   • 初始化流量 \(f\) 为零流，即所有边的流量为 0。
   • 计算残量图 \(G_f\)，其中每条边的残量容量为原容量减去当前流量。
   • 设置初始距离标签 \(d(v)\)（从顶点 \(v\) 到汇点 \(t\) 的最短路径估计，基于残量图）。

2. 容量缩放阶段

   • 算法按缩放参数 \(\Delta\) 分阶段进行。初始时 \(\Delta\) 设为大于等于最大容量 \(U\) 的最小 2 的幂次（例如 \(\Delta = 2^{\lceil \log_2 U \rceil}\))。
   • 每个阶段处理残量容量至少为 \(\Delta\) 的边，忽略容量较小的边。

3. 距离标签与容许边

   • 维护距离标签 \(d(v)\)，表示在残量图中从 \(v\) 到 \(t\) 的最短路径距离（按边数计算）。
   • 定义容许边：若边 \((u, v)\) 满足 \(d(u) = d(v) + 1\) 且残量容量 \(r(u, v) \geq \Delta\)，则该边为容许边。
   • 仅通过容许边推送流量，以确保流量沿最短路径方向移动。

4. 推送流量

   • 从源点 \(s\) 开始，沿容许边推送尽可能多的流量（不超过残量容量）。
   • 若某顶点 \(u\) 有超额流量（流入大于流出），但无可用的容许边，则重新标记 \(d(u)\) 为 \(\min\{d(v) + 1 \mid (u, v) \text{ 是残量边} \}\)，以创建新的容许边。
   • 重复推送和重新标记操作，直到无法从 \(s\) 到 \(t\) 推送更多流量。

5. 缩放参数更新

   • 当当前 \(\Delta\) 下无法推送更多流量时，将 \(\Delta\) 减半（即 \(\Delta \leftarrow \Delta / 2\)）。
   • 若 \(\Delta < 1\)，算法终止；否则返回步骤 2 处理新的残量图。

6. 终止与正确性

   • 当 \(\Delta < 1\) 时，所有边容量已精确处理，当前流量即为最大流。
   • 正确性由距离标签和容许边机制保证，确保流量始终沿最短路径递增，避免循环。

关键点

• 通过容量缩放减少每次处理的边数，提升效率。
• 距离标签确保流量推送方向正确，避免回溯。
• 时间复杂度优于传统算法，适用于稀疏图和大容量场景。