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

题目描述
Goldberg-Rao算法是一种用于求解有向图最大流问题的高效算法，特别适用于大规模稀疏图。给定一个带源点s和汇点t的有向图，每条边有一个非负容量c(e)，目标是找到从s到t的最大流量。Goldberg-Rao算法通过结合阻塞流（Blocking Flow）和容量缩放（Capacity Scaling）技术，将时间复杂度优化到O(min{√m, n^{2/3}} · m · log(n²/m) · log U)，其中U是最大边容量。

解题过程

1. 初始化

   • 设置初始流f(e)=0，计算残量图G_f（残量容量r(e)=c(e)-f(e)）。
   • 定义Δ为当前缩放参数，初始Δ=2^{⌊log₂U⌋}（即不小于U的最小2的幂）。

2. Δ-缩放阶段

   • 在残量图中，只保留残量容量r(e)≥Δ的边，形成图G_f(Δ)。
   • 若Δ<1，算法终止；否则进入下一步。

3. 计算Δ-近似最小割

   • 在G_f(Δ)上，通过BFS或DFS计算从s出发的强连通分量，将节点按到s的距离分层（若不可达则标记距离为∞）。
   • 定义d(v)为v到s的最短路径边数（只经过r(e)≥Δ的边），d(t)为关键值。

4. 寻找阻塞流

   • 在分层图（Level Graph）中，仅保留满足d(u)+1=d(v)的边(u,v)。
   • 使用DFS或Dinic风格的阻塞流算法，在分层图中找到一条从s到t的路径，并推送Δ单位的流量（因为所有边r(e)≥Δ）。
   • 重复直到s到t无路径，此时流f更新，残量图G_f同步调整。

5. 缩放参数更新

   • 当G_f(Δ)中s到t不连通时，将Δ减半：Δ=Δ/2。
   • 返回步骤2继续下一缩放阶段。

关键点说明

• 阻塞流：在分层图中无法再推送流量的流，确保每阶段至少增加流量Δ。
• 容量缩放：通过Δ逐步细化，避免在低容量边上浪费计算。
• 复杂度优势：通过分层和缩放组合，减少推送次数，尤其适合边容量差异大的图。

示例
假设图有边(s,a):3, (a,t):2, (s,b):2, (b,t):3，U=3，初始Δ=2。

• Δ=2时：残量边需r≥2，分层图包含(s,a),(a,t),(s,b),(b,t)。推送流2后，(a,t)和(s,b)残量变为0，移除。
• Δ=1时：在剩余边上推送流1，达到最大流3。

通过这种分阶段逼近，算法高效平衡了路径查找和流量增量。