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

题目描述
Goldberg-Rao算法是一种用于求解有向图最大流问题的高效算法，其时间复杂度为O(V²E log(U))，其中V是顶点数，E是边数，U是最大边容量。该算法结合了Push-Relabel框架和容量缩放思想，通过动态调整流推送的阈值来优化性能。问题要求：给定一个有向图G=(V,E)，源点s，汇点t，以及每条边的容量c(u,v)≥0，求从s到t的最大流值。

解题过程

1. 初始化

   • 设置初始流f(u,v)=0对所有边(u,v)∈E。
   • 为每个顶点u分配一个高度h(u)：h(s)=V，h(t)=0，其他顶点h(u)=0。
   • 初始化超额流e(u)：e(s)=∞（通过从s推流到邻居），其他顶点e(u)=0。
   • 定义参数Δ，初始时Δ为最大边容量的最小二次幂（即Δ=2^⌊log₂U⌋）。

2. 算法主循环（当Δ≥1）

   • 阶段1：Δ-缩放阶段
     • 仅考虑剩余容量r(u,v)=c(u,v)-f(u,v)≥Δ的边进行流操作。
     • 对每个超额顶点u（e(u)>0），尝试沿高度差h(u)=h(v)+1的边推流（Push操作），推流量为min(e(u), r(u,v))。
     • 若无可推流边，则提升顶点高度（Relabel操作），使其满足h(u)≤h(v)+1对所有剩余边成立。
   • 阶段2：Δ缩减
     • 当无超额顶点或所有剩余边r(u,v)<Δ时，将Δ减半（Δ=Δ/2），进入下一缩放阶段。
   • 重复直到Δ=0。

3. 关键优化

   • 高度标签约束：在Δ-缩放阶段，仅允许沿“Δ-可用边”（r(u,v)≥Δ）且满足h(u)=h(v)+1的边推流。
   • 全局重标记：定期使用BFS从汇点t更新高度，确保高度标签的有效性，避免无效操作。

4. 终止条件

   • 当Δ=0时，算法终止。此时汇点t的流入量即为最大流值。

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

• Δ=2阶段：从s推流2到a（剩余容量3≥2），a推流2到t；s推流2到b，b推流2到t。超额流清零，Δ减为1。
• Δ=1阶段：边(s,a)剩余容量1≥1，推流1到a，但a到t无剩余容量，触发重标记后无改进，Δ减为0终止。
  最大流=2+2=4。

通过缩放阈值Δ，算法优先处理高容量边，减少无效操作，兼顾效率与正确性。