xxx 最大流问题（Goldberg-Rao算法） 题目描述 给定一个有向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个非负容量 \( c(e) \)。指定源点 \( s \) 和汇点 \( t \)，求从 \( s \) 到 \( t \) 的最大流。Goldberg-Rao 算法是一种高效的最大流算法，在最坏情况下时间复杂度为 \( O(|E| \cdot \min(|V|^{2/3}, |E|^{1/2}) \cdot \log(|V|^2 / |E|) \cdot \log U) \)，其中 \( U \) 是最大边容量。该算法结合了容量缩放和最短路径距离的思想，适用于大容量图。 解题过程 基本概念回顾 流（Flow） ：满足容量限制（\( 0 \leq f(e) \leq c(e) \)）和流量守恒（除 \( s, t \) 外流入等于流出）的边函数。 残量图（Residual Graph） ：包含原边（剩余容量 \( c(e) - f(e) \)）和反向边（容量为 \( f(e) \)）。 距离标签（Distance Label） ：每个节点 \( v \) 到汇点 \( t \) 的估计距离 \( d(v) \)，满足 \( d(t) = 0 \) 和残量图中边 \( (u,v) \) 有 \( d(u) \leq d(v) + 1 \)。 算法框架 Goldberg-Rao 算法是 Push-Relabel 算法的改进，核心步骤包括： 初始化 ：设置距离标签 \( d(v) \) 为 \( v \) 到 \( t \) 的最短路径长度（按边数），流 \( f \) 初始为 0。 循环迭代 ：重复以下步骤直到无法改进： a. 在残量图中找到“允许边”（满足 \( d(u) = d(v) + 1 \) 的边）。 b. 沿允许边推送流（Push 操作），或若无法推送则提升节点标签（Relabel 操作）。 创新点 ：引入容量缩放和“Δ-残量图”来优化推送过程。 Δ-残量图与容量缩放 设当前缩放参数为 \( Δ \)（初始为 \( 2^{\lfloor \log_ 2 U \rfloor} \)）。 定义 Δ-残量图 ：仅保留剩余容量 ≥ Δ 的边。 在 Δ-残量图中计算距离标签 \( d_ Δ(v) \)（到 \( t \) 的最短路径边数）。 仅当边 \( (u,v) \) 满足 \( d_ Δ(u) = d_ Δ(v) + 1 \) 且剩余容量 ≥ Δ 时，才允许推送流。 推送流规则 从标签较高的节点向较低标签的邻居推送流。 推送量取以下最小值： 边的剩余容量； 节点的超额流（流入减流出）； 当前缩放参数 Δ。 若节点无法推送流但仍有超额流，则提升其距离标签（设为邻居最小标签 +1）。 缩放参数更新 当 Δ-残量图中不存在 \( s \to t \) 路径时，将 Δ 减半（Δ ← Δ/2）。 重复步骤 3-5 直到 Δ < 1，此时算法终止。 示例说明 考虑图：边 \( (s,a):3, (a,t):2, (s,b):2, (b,t):3 \)，容量均为整数。 初始化：Δ=4（因最大容量 3，取 \( 2^{\lfloor \log_ 2 3 \rfloor} = 2 \)，但为演示设 Δ=4）。 迭代 1（Δ=4）：无剩余容量 ≥4 的边，直接 Δ←2。 迭代 2（Δ=2）： 推送流：从 \( s \) 推 2 到 \( a \)，再从 \( a \) 推 2 到 \( t \)；同时从 \( s \) 推 2 到 \( b \)，再从 \( b \) 推 2 到 \( t \)。 总流 = 4，达到最大流。 复杂度与优势 通过容量缩放减少无效推送，每次缩放阶段最多 \( O(|V|^2) \) 次推送。 标签计算使用 BFS，保证高效性。 适用于边容量差异大的图，比传统 Dinic 或 Edmonds-Karp 算法更高效。 总结 Goldberg-Rao 算法通过结合容量缩放和距离标签，优化了流的推送方向，减少了冗余操作。其核心思想是逐步细化流量单位（Δ），并在每个缩放阶段利用最短路径信息指导流推送，最终高效求得最大流。