基于线性规划的图最大流问题的多项式时间容量缩放推流-重标算法求解示例 这是一个关于最大流问题的算法。最大流问题是在一个有向图中，从源点s到汇点t，在每条边有容量限制的条件下，寻找能从s发送到t的最大流量。Ford-Fulkerson方法是基础，但其时间复杂度依赖于容量值，不是强多项式时间的。 容量缩放（Capacity Scaling） 是结合了 推流-重标（Push-Relabel） 框架的一种优化技术，它能确保算法在多项式时间内运行。我们通过一个具体例子来理解。 1. 问题描述 我们有一个有向图 \(G = (V, E)\)，其中 \(|V| = n\)， \(|E| = m\)。 每条边 \((u, v) \in E\) 有一个非负整数容量 \(c(u, v)\)。 有两个特殊顶点：源点 \(s\) 和汇点 \(t\)。 一个 流 是一个函数 \(f: E \rightarrow R^+\)，满足： 容量限制：对所有边 \((u, v)\)，有 \(0 \le f(u, v) \le c(u, v)\)。 流量守恒：对所有顶点 \(v \in V \setminus \{s, t\}\)，有 \(\sum_ {(u, v) \in E} f(u, v) = \sum_ {(v, w) \in E} f(v, w)\)。 目标 是最大化从 \(s\) 流出的总流量，即最大流的值 \(|f| = \sum_ {(s, v) \in E} f(s, v)\)。 示例图 ： 顶点集 V = {s, a, b, t} 边集 E 和容量 c 如下： (s, a): 容量 3 (s, b): 容量 2 (a, b): 容量 1 (a, t): 容量 2 (b, t): 容量 3 (可以画一个草图：s在上方，a在左下方，b在右下方，t在最下方。s指向a和b，a指向b和t，b指向t) 2. 算法核心思想：推流-重标 (Push-Relabel) 在讲解容量缩放之前，必须先理解Push-Relabel（或称Preflow-Push）算法。它与Ford-Fulkerson的“寻找增广路”思路不同。 关键定义 ： 预流 (Preflow) ： 放宽流量守恒条件，允许顶点有“盈余”。即对于任何非源顶点v，允许 流入量 ≥ 流出量 。其差值称为该顶点的 超额流 (excess flow) ，记作 \(e(v) \ge 0\)。源点s没有此限制，通常初始化时让它“流出”尽可能多，产生盈余。 高度函数 (Height/Label) ： 为每个顶点v分配一个整数高度 \(h(v)\)。初始化：\(h(s)=n, h(t)=0\)，其他顶点 \(h(v)=0\)。我们只沿“下坡”方向推流：即从高顶点推流向低顶点。 可行边 (Admissible Edge) ： 对于一条残量边（有剩余容量的边）\((u, v)\)，如果 \(h(u) = h(v) + 1\)，则称它是 可行 的。 基本操作 ： 推流 (Push) ： 如果顶点u有盈余 (\(e(u)>0\))，且存在一条从u出发的可行边(u, v)，则可以将一部分超额流沿此边推出去。推流量为 \(\Delta = \min(e(u), r(u, v))\)，其中 \(r(u, v) = c(u, v) - f(u, v)\) 是残量容量。这可能会增加v的盈余。 重标 (Relabel) ： 如果顶点u有盈余，但从u出发的所有残量边都指向高度大于等于 \(h(u)\) 的顶点（即没有“下坡”可走），则我们提高u的高度：设置 \(h(u) = 1 + \min\{h(v) | (u, v) 是残量边\}\)。这为后续推流创造了“下坡”。 算法不断执行推流和重标操作，直到除s和t外所有顶点的超额流都变为0。此时，预流就变成了一个最大流。 复杂度 ： 基本的Push-Relabel算法是 \(O(n^2 m)\)，已经是强多项式时间。但我们可以做得更好。 3. 容量缩放 (Capacity Scaling) 的引入 容量缩放是一种通用优化策略，其核心思想是“ 先处理大流，再处理小流 ”。我们不是一次处理所有可能的流，而是从一个很大的 缩放参数Δ 开始，Δ初始化为一个大于最大容量的2的幂（例如 \(2^{\lfloor \log_ 2 C \rfloor}\)，C是最大边容量）。在每一轮缩放阶段，我们只考虑那些残量容量至少为Δ的“大”边，并在由这些边构成的子图上执行推流操作。当无法再推送Δ量级的流时，将Δ减半，进入下一轮。直到Δ <1，算法结束。 为什么有效 ： 它避免了在容量很小的边上进行大量无效的、小流量的推流操作。 由于Δ呈指数级下降，总轮数为 \(O(\log C)\)。 在每一轮中，推流操作的总次数可以被有效限制，从而得到总的时间复杂度为 \(O(nm \log C)\) 或更好的界。 与Push-Relabel结合 ： 在每一轮缩放阶段Δ下，我们运行一个修改版的Push-Relabel算法。我们只关注那些残量容量 \(r(u, v) \ge Δ\) 的边。推流操作只有当可以推送至少Δ单位的流量时才执行（即“Δ-推流”），这保证了每次推流都显著减少盈余。 4. 逐步求解示例 我们使用示例图，并应用 基于容量缩放的推流-重标算法 。 步骤0：初始化 找出最大边容量 \(C = \max\{3, 2, 1, 2, 3\} = 3\)。 计算初始缩放参数 \(Δ = 2^{\lfloor \log_ 2 3 \rfloor} = 2^1 = 2\)。 初始化流 \(f = 0\) 对所有边。 初始化高度： \(h(s)=4\) (n=4), \(h(a)=0, h(b)=0, h(t)=0\)。 初始化预流： 从s出发，沿每条边推送等于其容量的流（但受Δ限制？不完全是，在初始化时，我们通常从s沿着残量容量≥Δ的边推送尽可能多的流，但不超过容量）。更标准的做法是：在第一轮Δ=2时，我们只考虑容量≥2的边来构建初始预流。 边 (s,a): 容量3 ≥ 2，从s推送 min(容量, 一个很大的数) 的流。为简单起见，我们像标准Push-Relabel一样初始化：对每条从s出发的边，设置 \(f(s,v) = c(s,v)\)，即饱和这些边。但这会超过Δ限制吗？在缩放算法中，初始化时我们通常用Δ来限制推送量，但为了演示，我们采用简化逻辑：在每一轮开始时，我们有一个当前的流f，然后在本轮Δ下，我们只考虑那些残量容量r(u,v) ≥ Δ的边来进行推流-重标操作。 为了清晰，我们一步步来： 全局初始化 （与Δ无关，只做一次）： 设 f = 0。 设 h(s)=4, h(a)=h(b)=h(t)=0。 对每条从s出发的边 (s,v)，执行饱和推送：推送量 d = c(s,v)。这使s的盈余为负（我们不关心），并使v获得盈余 e(v)=c(s,v)。 Push(s, a): f(s,a)=3, e(a)=3. Push(s, b): f(s,b)=2, e(b)=2. e(s) = -(3+2) = -5 (我们通常不跟踪源汇盈余)。 当前盈余顶点：a(3), b(2)。 现在我们进入 容量缩放的主循环 ，从 Δ=2 开始。 第一轮缩放阶段：Δ = 2 规则 ： 在这一阶段，我们只考虑那些 残量容量 r(u,v) = c(u,v) - f(u,v) ≥ 2 的边，并只在这样的边上执行推流/重标操作。如果残量容量 < 2，则在本轮视为“堵塞”，忽略。 计算当前残量容量 r： r(s,a)=3-3=0 ( <2) 忽略 r(s,b)=2-2=0 ( <2) 忽略 r(a,b)=1-0=1 ( <2) 忽略 r(a,t)=2-0=2 (≥2) 可行 r(b,t)=3-0=3 (≥2) 可行 注意，反向边 (a,s), (b,s) 的残量容量是正向流的值，分别是3和2，都≥2。但反向边只在高度允许时（h(v) = h(u)+1）才可能成为可行边。目前h(a)=0, h(s)=4，所以(a,s)不可能可行（因为需要h(a)=h(s)+1=5）。 当前活跃（有盈余）顶点：a(3), b(2)。 检查可行边（残量≥2 且 h(u) = h(v)+1）： 对于a: h(a)=0。其残量≥2的边只有(a,t)，需要h(a)=h(t)+1，即0=0+1？不成立。所以a没有可行边。执行 重标(Relabel) : 查看从a出发的所有残量边（包括容量<2的吗？在缩放轮次中，重标时检查的邻居v通常基于 所有残量边 ，而不仅仅是r≥Δ的边。但为了性能，有些实现只考虑r≥Δ的边。我们按标准描述：重标时考虑所有残量边）。 从a出发的残量边： (a,b): r=1, (a,t): r=2, (a,s): r=3（反向边）。 这些边指向的顶点高度： h(b)=0, h(t)=0, h(s)=4。 min{h(v)} = 0。所以新高度 h(a) = 1 + 0 = 1。 对于b: h(b)=0。残量≥2的边有(b,t): r=3，需要h(b)=h(t)+1 => 0=1? 不成立。所以b没有可行边。重标(b)： 从b出发的残量边： (b,t): r=3, (b,a): r=0? 反向边(b,a)的容量是0，正向流是0，所以残量是正向容量1减去流0，等于1？不对，边是(a,b)有容量1，不是(b,a)。所以(b,a)不是原图中的边，其残量容量是当前从b到a的反向流，即f(a,b)=0，所以残量=0。所以从b出发的残量边只有(b,t): r=3, (b,s): r=2（反向边）。 邻居高度： h(t)=0, h(s)=4。 min=0。 新高度 h(b) = 1 + 0 = 1。 现在高度： h(s)=4, h(a)=1, h(b)=1, h(t)=0。 检查可行边（残量≥2且h(u)=h(v)+1）： a: h(a)=1。边(a,t): h(t)=0, 满足 1 = 0+1 且 r(a,t)=2≥2。 可行 。执行推流Push(a,t): 可推量 Δ' = min(e(a)=3, r(a,t)=2) = 2。推流2单位。 f(a,t) 从0变为2。 e(a) 从3变为1。 e(t) 从0变为2（但汇点盈余我们不主动处理，算法最后会变成流的一部分）。 更新残量： r(a,t) 从2变为0，反向边r(t,a)从0变为2。 a 还有盈余1。现在检查a的可行边： (a,t)残量变为0(<2)不再考虑。 (a,s)是反向边，h(a)=1, h(s)=4，不满足h(a)=h(s)+1。 (a,b)残量1 <2不考虑。所以a无可行边。重标(a)： 邻居高度： b(1), t(0), s(4)。 min=0。 h(a) = 1+0 = 1（没变？min是0，h(a)变成1，和原来一样。这通常不会发生，因为之前有边(a,t)满足h(a)=h(t)+1，但它的残量现在为0，所以重标时会忽略它。min{h(v) | 残量边>0} = min{ h(b)=1 (r(a,b)=1>0), h(s)=4 (r(a,s)=3>0), h(t)=0 (但r(a,t)=0, 不满足>0) } = 1。所以新高度 h(a)=1+1=2。) 修正后，h(a)=2。 b: h(b)=1。边(b,t): h(t)=0, 满足 1 = 0+1 且 r(b,t)=3≥2。可行。推流Push(b,t): Δ' = min(e(b)=2, r=3) = 2。 f(b,t) 从0变为2。 e(b) 从2变为0。 e(t) 增加2，变为4。 r(b,t) 从3变为1 ( <2)，反向边r(t,b)从0变为2。 现在盈余顶点： a(1), b(0)。b的盈余为0，变为不活跃。 检查a: h(a)=2。可行边？ (a,b): r=1<2 忽略。 (a,s): h(s)=4, 不满足条件。 (a,t): r=0 忽略。所以无可行边。重标(a)： 邻居b(1), s(4), t(0)。具有正残量的边： (a,b): r=1>0, (a,s): r=3>0。 min{h(b)=1, h(s)=4} = 1。 h(a)=1+1=2（不变）。说明a被“卡住”了？但它的盈余>0。实际上，这是因为在Δ=2的尺度下，从a出发没有残量≥2的边了。所以a的盈余无法在本轮被推送。这正是容量缩放的特点：小的盈余（此处为1， <Δ）留到下一轮Δ更小时处理。 此时，在Δ=2的尺度下，没有活跃顶点（b盈余0，a盈余1但无Δ-可行边）可以继续操作。我们结束Δ=2这一轮。 当前流状态： f(s,a)=3, f(s,b)=2, f(a,b)=0, f(a,t)=2, f(b,t)=2。 总流值 = f(s,a)+f(s,b) = 5? 不，流出s的是5，但流入t的是4，因为有1单位卡在a。这是一个预流，不是合法流。 第二轮缩放阶段：Δ = Δ/2 = 1 更新缩放参数Δ=1。现在规则放宽：我们考虑所有残量容量 r(u,v) ≥ 1 的边。 计算残量： r(s,a)=0 ( <1) r(s,b)=0 ( <1) r(a,b)=1-0=1 (≥1) r(a,t)=0 ( <1) r(b,t)=3-2=1 (≥1) 反向边： r(a,s)=3 (≥1), r(b,s)=2 (≥1), r(t,a)=2 (≥1), r(t,b)=2 (≥1)。 盈余顶点： a(1), b(0)。b无盈余，从a开始。 高度当前： h(s)=4, h(a)=2, h(b)=1, h(t)=0。 检查a的可行边（r≥1且h(u)=h(v)+1）： (a,b): r=1, h(a)=2, h(b)=1, 满足 2 = 1+1。可行。执行推流Push(a,b): Δ' = min(e(a)=1, r=1) = 1。 f(a,b) 从0变为1。 e(a) 从1变为0。 e(b) 从0变为1。 更新残量： r(a,b) 从1变为0，反向边r(b,a)从0变为1。 现在a盈余为0，b盈余为1。 检查b的可行边（r≥1）： (b,t): r=1, h(b)=1, h(t)=0, 满足 1 = 0+1。可行。推流Push(b,t): Δ' = min(e(b)=1, r=1) = 1。 f(b,t) 从2变为3。 e(b) 从1变为0。 e(t) 增加1，变为5。 r(b,t) 从1变为0，反向边r(t,b)从2变为3。 现在所有非源非汇顶点（a和b）的盈余都为0！预流变成了一个有效的流。 当前流： f(s,a)=3, f(s,b)=2, f(a,b)=1, f(a,t)=2, f(b,t)=3。 验证守恒： 对于a: 流入 = f(s,a)=3； 流出 = f(a,b)+f(a,t)=1+2=3。守恒。 对于b: 流入 = f(s,b)+f(a,b)=2+1=3； 流出 = f(b,t)=3。守恒。 这是一个合法的流，其值 |f| = 流出s = 3+2 = 5，也等于流入t = 2+3 = 5。 由于Δ=1/2后小于1（下一轮Δ=0.5 <1），算法结束。 5. 结论 我们通过容量缩放推流-重标算法，得到了该图的最大流，值为5。算法的步骤是： 初始化预流和高度。 从较大的Δ（2的幂）开始，每一轮只在残量容量≥Δ的边上执行推流-重标操作，推送至少Δ单位的流量。 当一轮无法再推进时，将Δ减半，重复步骤2。 当Δ < 1时，所有顶点盈余为0，得到最大流。 这个方法结合了Push-Relabel的高效性和容量缩放的粗粒度到细粒度的优化，达到了 \(O(nm \log C)\) 的时间复杂度，是求解最大流问题的经典强多项式算法之一。