最大流问题（Goldberg-Rao 算法） 我将为您讲解 Goldberg-Rao 算法，这是一个用于求解最大流问题的高效算法。该算法结合了推送-重标（Push-Relabel）框架和容量缩放（Capacity Scaling）技术，在最坏情况下具有优异的时间复杂度。 问题描述 最大流问题：给定一个有向图 G=(V,E)，其中每条边 (u,v)∈E 有一个非负容量 c(u,v)≥0，以及源点 s 和汇点 t。目标是找到一个从 s 到 t 的流函数 f，满足容量限制（f(u,v)≤c(u,v)）和流量守恒（除 s 和 t 外，流入每个顶点的流量等于流出该顶点的流量），并且使得从 s 流出的总流量最大化。 Goldberg-Rao 算法核心思想 该算法是推送-重标算法的一种优化版本，通过引入“Δ-残差图”和“位缩放”技术来改进性能。其核心步骤包括： 维护一个尺度参数 Δ，初始为最大边容量的幂次。 在 Δ-残差图中（只包含残差容量 ≥Δ 的边），执行受限的推送-重标操作。 当 Δ-残差图中不存在可行操作时，将 Δ 减半，重复直到 Δ <1。 详细解题步骤 步骤 1: 初始化 设置初始流 f 为 0。 计算初始尺度参数 Δ = 2^⌊log₂U⌋，其中 U 是图中最大边容量。 初始化每个顶点的高度（标签）h(v)=0（源点 s 的高度可设为 |V|，汇点 t 的高度为 0）。 初始化每个顶点的超额流（excess flow）e(v)=0，并通过从 s 推流到其邻居，使 s 的邻居获得初始超额流。 步骤 2: 主循环（当 Δ ≥ 1） 构建 Δ-残差图 G_ f(Δ) ：只保留残差容量 r(u,v) = c(u,v) - f(u,v) ≥ Δ 的边。 在 G_ f(Δ) 中执行推送-重标操作 ： 推送操作 ：对于超额流 e(u) > 0 的顶点 u，如果存在边 (u,v) 在 G_ f(Δ) 中，且 h(u) = h(v) + 1，则沿 (u,v) 推送 min(e(u), r(u,v)) 的流量。推送后更新 e(u) 和 e(v)。 重标操作 ：如果 u 有超额流但无法推送（即没有满足条件的边），则将其高度 h(u) 设置为 min{ h(v) + 1 | (u,v) 在 G_ f(Δ) 中 }（若无边，则设 h(u) = h(u) + 1）。 当 G_ f(Δ) 中无法再进行推送或重标时 ，将 Δ 减半（Δ = Δ / 2），并更新 G_ f(Δ) 以包含残差容量 ≥ 新 Δ 的边。 步骤 3: 终止 当 Δ < 1 时，算法终止。此时的流 f 即为最大流。 关键优化与注意事项 高度差限制 ：在 Δ-残差图中，只允许高度差为 1 的边进行推送，这避免了频繁的重标操作。 Δ 的缩放 ：通过逐步减半 Δ，算法优先处理高容量边，快速减少超额流，从而提高效率。 时间复杂度 ：Goldberg-Rao 算法的最坏时间复杂度为 O(min{ |V|^{2/3}, |E|^{1/2} } * |E| * log(U) * log(|V|²/|E|))，优于许多传统最大流算法。 示例说明 考虑一个简单图：顶点集 {s, a, b, t}，边容量为 c(s,a)=3, c(s,b)=2, c(a,b)=1, c(a,t)=2, c(b,t)=3。 初始化 Δ=4（因为 U=3，2^⌊log₂3⌋=2，但算法常取大于 U 的最小 2 的幂，这里为 4），流 f=0。 Δ=4 时，G_ f(4) 无边（因所有残差容量均 <4），直接减半至 Δ=2。 Δ=2 时，G_ f(2) 包含边 (s,a)、(s,b)、(b,t)（残差容量≥2）。执行推送：从 s 推流到 a 和 b，再推流到 t。 减半 Δ 至 1，处理剩余低容量边（如 (a,b)），最终得到最大流值 4。 通过这种分尺度处理，Goldberg-Rao 算法高效地平衡了全局和局部优化，适用于大规模网络流问题。