基于线性规划的图最大流问题的多项式时间容量缩放推流-重标算法求解示例 题目描述 ： 考虑一个有向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合（\( |V| = n \)，\( |E| = m \) ），每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \)。指定一个源点 \( s \in V \) 和一个汇点 \( t \in V \)。图的最大流问题目标是找到从 \( s \) 到 \( t \) 的最大可能流量，满足以下约束： 容量约束：每条边上的流量不超过其容量。 流量守恒：除 \( s \) 和 \( t \) 外，每个顶点的流入等于流出。 传统算法如 Ford–Fulkerson 可能在边容量为无理数时无法保证终止，而 Edmonds–Karp 算法（基于最短增广路）的复杂度为 \( O(n m^2) \)。本题目要求使用一种多项式时间的高效算法—— 容量缩放的推流-重标（Capacity-Scaling Push-Relabel）算法 求解最大流，其核心思想是通过逐步降低容量阈值 \( \Delta \)，每次仅处理剩余网络中容量不低于 \( \Delta \) 的边，从而在 \( O(m^2 \log C) \) 时间内找到最大流（\( C \) 为最大边容量）。我们将从算法原理、步骤、正确性及实例演示展开讲解。 解题过程 ： 1. 算法背景与核心思想 推流-重标算法（Push-Relabel）是一种高效的最大流算法，它不维护流量守恒的可行流，而是允许顶点有“超额流量”（excess flow），通过局部“推流”和“重标高度”操作逐步将流量推向汇点。 容量缩放（Capacity-Scaling）是优化策略，通过处理高容量边优先，减少不必要的操作。设定一个缩放参数 \( \Delta \)，初始为 \( 2^{\lfloor \log_ 2 C \rfloor} \)（即不大于最大容量的最大 2 的幂）。在每轮缩放中，只考虑剩余容量 \( r(u, v) \geq \Delta \) 的边进行推流，当无法再推流时，将 \( \Delta \) 减半，重复直至 \( \Delta < 1 \)。 该算法结合了推流-重标的高效性和容量缩放对边数的限制，达到 \( O(m^2 \log C) \) 的时间复杂度（若用动态树优化可至 \( O(mn \log C) \)，但本例展示基础版本）。 2. 算法步骤详解 步骤 1：初始化 设 \( f(u, v) = 0 \) 为当前流量，\( r(u, v) = c(u, v) \) 为剩余容量。 对每个顶点 \( v \in V \)，设高度标签 \( h(v) = 0 \)，超额流量 \( e(v) = 0 \)。 初始化源点高度：\( h(s) = n \)（保证源点高度始终最高之一）。 从源点 \( s \) 向所有邻居推流：对每条边 \( (s, v) \in E \)，推流量 \( \min(c(s, v), c(s, v)) \) 到 \( v \)，即设置 \( f(s, v) = c(s, v) \)，\( e(v) = c(s, v) \)，\( e(s) \) 相应减少（实际上 \( e(s) \) 初始为负，表示流出）。 设定缩放参数 \( \Delta = 2^{\lfloor \log_ 2 C \rfloor} \)。 步骤 2：容量缩放主循环（当 \( \Delta \geq 1 \) 时） 在每轮 \( \Delta \) 下，只考虑剩余容量 \( r(u, v) \geq \Delta \) 的边构成的子图 \( G_ \Delta \)。 在 \( G_ \Delta \) 上执行推流-重标操作，直到除 \( s, t \) 外所有顶点 \( e(v) = 0 \)（即无超额流量）。 推流操作（Push(u, v)）：如果顶点 \( u \) 有超额流量 \( e(u) > 0 \)，且边 \( (u, v) \) 在 \( G_ \Delta \) 中（即 \( r(u, v) \geq \Delta \)），并且 \( h(u) = h(v) + 1 \)（高度差为 1），则从 \( u \) 向 \( v \) 推流量 \( \delta = \min(e(u), r(u, v)) \)。更新： \( f(u, v) = f(u, v) + \delta \)，\( f(v, u) = f(v, u) - \delta \)（反向边增加剩余容量）， \( e(u) = e(u) - \delta \)，\( e(v) = e(v) + \delta \)， \( r(u, v) = r(u, v) - \delta \)，\( r(v, u) = r(v, u) + \delta \)。 重标操作（Relabel(u)）：如果 \( u \) 有超额流量 \( e(u) > 0 \)，但在 \( G_ \Delta \) 中不存在满足 \( h(v) < h(u) \) 且 \( r(u, v) \geq \Delta \) 的邻居 \( v \)，则升高 \( u \) 的高度：\( h(u) = 1 + \min\{ h(v) : (u, v) \in E, r(u, v) \geq \Delta \} \)。 重复选择有超额流量的顶点（除 \( s, t \) 外）进行推流或重标，直到无法操作。 当 \( G_ \Delta \) 中无超额流量时，将 \( \Delta \) 减半：\( \Delta = \Delta / 2 \)。 步骤 3：终止与输出 当 \( \Delta < 1 \) 时，算法终止。此时流量 \( f \) 是最大流，因为剩余网络中无增广路（由高度标签和超额流量为零保证）。 最大流值为汇点 \( t \) 的流入量，或源点 \( s \) 的流出量。 3. 实例演示 考虑简单有向图：\( V = \{s, a, b, t\} \)，边与容量为： \( (s, a): 3, (s, b): 2, (a, b): 1, (a, t): 2, (b, t): 3 \)。 最大容量 \( C = 3 \)，初始 \( \Delta = 2^{\lfloor \log_ 2 3 \rfloor} = 2 \)。 初始化 ： 流量全为零。高度：\( h(s) = 4 \), \( h(a)=h(b)=h(t)=0 \)。超额流量：从 \( s \) 推流到邻居：沿 \( (s, a) \) 推 \( \min(3, 3) = 3 \)，\( e(a)=3 \)，沿 \( (s, b) \) 推 2，\( e(b)=2 \)，\( e(s) = -5 \)。剩余容量更新。 当前 \( \Delta = 2 \)，构建 \( G_ \Delta \)：只含剩余容量 \( \geq 2 \) 的边。初始时，\( r(s, a)=3 \geq 2 \)，\( r(s, b)=2 \geq 2 \)，\( r(a, t)=2 \geq 2 \)，\( r(b, t)=3 \geq 2 \)，边 \( (a, b) \) 容量 1 不包含。 第一轮缩放（Δ=2） ： 选择超额顶点 \( a \)：在 \( G_ \Delta \) 中，邻居 \( t \) 满足 \( h(a)=0, h(t)=0 \)，高度差不为 1，无法推流。检查所有邻居：无满足 \( h(v) < h(a) \) 且 \( r(a, v) \geq 2 \) 的边，故重标 \( a \)：最小邻居高度为 \( h(t)=0 \)，所以 \( h(a) = 0+1=1 \)。 现在 \( a \) 可向 \( t \) 推流（因为 \( h(a)=1, h(t)=0 \)，差为 1）：推流量 \( \delta = \min(e(a)=3, r(a, t)=2) = 2 \)。更新后 \( e(a)=1 \), \( e(t)=2 \), \( r(a, t)=0 \)，该边从 \( G_ \Delta \) 移除。 顶点 \( a \) 仍有超额流量 1，但在 \( G_ \Delta \) 中无其他满足条件的邻居（\( (a, b) \) 不在 \( G_ \Delta \)），故重标 \( a \)：邻居在 \( G_ \Delta \) 中无，高度不变？实际检查所有边（包括不在 \( G_ \Delta \) 的）：\( (a, b) \) 剩余容量 1 但 \( <2 \)，不满足，所以无合适邻居，重标使 \( h(a) = 1 + \min(\emptyset) \) 理论上设为 \( n=4 \) 或保持，但算法中若无非饱和边，高度不升。这里我们继续处理其他顶点。 选择顶点 \( b \)：在 \( G_ \Delta \) 中，邻居 \( t \) 满足 \( h(b)=0, h(t)=0 \) 高度差不为 1，无法推流。重标 \( b \)：最小邻居高度 \( h(t)=0 \)，所以 \( h(b)=1 \)。 现在 \( b \) 可向 \( t \) 推流：推流量 \( \delta = \min(e(b)=2, r(b, t)=3) = 2 \)。更新后 \( e(b)=0 \), \( e(t)=4 \), \( r(b, t)=1 \)，该边从 \( G_ \Delta \) 移除（剩余容量 1 <2）。 此时 \( G_ \Delta \) 中边只剩 \( (s, a) \) 和 \( (s, b) \)，但 \( a \) 仍有超额流量 1，检查 \( G_ \Delta \) 中从 \( a \) 出发的边：无（因 \( (a, t) \) 容量 0，\( (a, b) \) 不在 \( G_ \Delta \)），所以重标 \( a \) 可能升高。实际上，算法会继续直到无超额流量：顶点 \( a \) 无法推流，高度升高至 2 后可能通过反向边推回？但反向边容量为 0 在 \( G_ \Delta \) 中不满足 ≥2。因此，此轮缩放结束条件为：除 \( s, t \) 外顶点 \( a \) 有超额流量但无法在 \( G_ \Delta \) 中操作，所以提前结束本轮缩放，将 \( \Delta \) 减半至 1。 第二轮缩放（Δ=1） ： 现在 \( G_ \Delta \) 包含所有剩余容量 ≥1 的边。当前剩余容量：\( r(s, a)=3 \), \( r(s, b)=2 \), \( r(a, b)=1 \), \( r(b, t)=1 \), 其他为 0。超额流量：\( e(a)=1 \), \( e(b)=0 \), \( e(t)=4 \)。 处理顶点 \( a \)：在 \( G_ \Delta \) 中，邻居 \( b \) 满足 \( h(a)=2, h(b)=1 \) 高度差为 1，可推流。推流量 \( \delta = \min(e(a)=1, r(a, b)=1) = 1 \)。更新后 \( e(a)=0 \), \( e(b)=1 \), \( r(a, b)=0 \)。 顶点 \( b \) 现超额 1：邻居 \( t \) 满足 \( h(b)=1, h(t)=0 \) 差为 1，推流量 \( \delta = \min(e(b)=1, r(b, t)=1) = 1 \)。更新后 \( e(b)=0 \), \( e(t)=5 \), \( r(b, t)=0 \)。 所有非源汇顶点超额为零，缩放结束。最终流量：\( f(s, a)=3 \), \( f(s, b)=2 \), \( f(a, b)=1 \), \( f(a, t)=2 \), \( f(b, t)=3 \)。最大流值 = 5。 4. 算法正确性与复杂度分析 正确性：容量缩放保证了每轮仅在较高容量边上推流，避免低容量边的频繁操作。当 \( \Delta < 1 \) 时，剩余网络中无边可通，算法终止，此时流为最大流（依据最大流最小割定理）。 复杂度：每轮缩放中，推流操作次数为 \( O(mn) \)，重标操作次数为 \( O(n^2) \)，共有 \( O(\log C) \) 轮缩放，总复杂度 \( O(mn \log C) \)。本例简化版本为 \( O(m^2 \log C) \)。该算法是强多项式时间的（依赖于 \( m, n \) 而非容量值）。 5. 总结 容量缩放推流-重标算法通过“高度标签”管理流向、“缩放阈值”筛选高容量边，高效求解最大流。其优势在于实践中速度快且易于实现，是许多高效最大流算法的基础。