最大流问题（Push-Relabel 算法的 Gap Relabeling 优化）

字数 3116 2025-12-08 16:07:17

最大流问题（Push-Relabel 算法的 Gap Relabeling 优化）

题目描述

我们有一个有向图 \(G = (V, E)\)，每条边有容量 \(c(u,v) \ge 0\)，指定源点 \(s\) 和汇点 \(t\)。
目标是找到从 \(s\) 到 \(t\) 的最大流。

Push-Relabel 算法 是求解最大流的经典方法之一，时间复杂度可达 \(O(V^2 \sqrt{E})\) 或 \(O(V^3)\)，但它可以通过多种启发式优化来提升性能。
其中 Gap Relabeling 是一种优化策略，可以在某些情况下减少不必要的操作，从而加速算法。

解题步骤

1. Push-Relabel 算法回顾（不包含 Gap 优化）

Push-Relabel 算法不维持流的守恒性（除了源和汇），而是维护：

超额流 \(e(u)\)：进入节点 \(u\) 的流量多于离开的流量时，\(e(u) > 0\)。
高度 \(h(u)\)：每个节点有一个整数高度，满足：
1. \(h(s) = |V|\)，\(h(t) = 0\)（初始化时）。
2. 对于残量边 \((u,v)\)，有 \(h(u) \le h(v) + 1\)（高度约束）。

算法重复执行两种基本操作：

Push(u, v)：
- 如果 \(e(u) > 0\)，残量边 \((u,v)\) 的残量容量 \(r(u,v) > 0\)，且 \(h(u) = h(v) + 1\)。
- 推送的流量 \(\Delta = \min(e(u), r(u,v))\)。
- 更新 \(e(u)\)、\(e(v)\)、残量容量。
Relabel(u)：
- 如果 \(e(u) > 0\)，且对所有残量边 \((u,v)\) 有 \(h(u) \le h(v)\)（无法直接推送）。
- 将 \(h(u)\) 设为 \(\min\{ h(v) \mid (u,v) \text{ 是残量边} \} + 1\)。

初始化时，从 \(s\) 向所有邻居推送尽可能多的流量（使其饱和），并设置 \(h(s) = |V|\)，其他节点高度为 0。

2. Gap Relabeling 的动机

观察高度引理：在算法运行中，对于任意高度 \(k\)，高度为 \(k\) 的节点数量不会变为 0 后再重新出现新的高度为 \(k\) 的节点，除非存在一个“间隙”。
但如果在某个时刻，没有节点具有高度 \(m\)，而存在节点高度 \(> m\) 且 \(< |V|\)，则这些节点无法将流送到汇点（因为高度差约束无法满足），可以直接将其高度提升到 \(|V|+1\)，从而让超额流快速退回源点，减少无效操作。

定义 Gap：
设高度标签范围是 \(0\) 到 \(2|V|-1\)（实际可达高度不超过 \(2|V|-1\)）。
如果高度 \(k\) 没有节点，且存在节点高度在 \((k, |V|]\) 之间，则称出现一个 Gap。

3. Gap Relabeling 优化步骤

在 Push-Relabel 算法中，维护一个数组 \(\text{count}[k]\) 记录当前高度为 \(k\) 的节点数量。

当执行 Relabel(u) 时：

设旧高度 \(old = h(u)\)。
将 \(h(u)\) 提升到新高度 \(new\)。
更新 \(\text{count}[old]\) 减 1，\(\text{count}[new]\) 加 1。
如果 \(\text{count}[old]\) 变为 0，且 \(0 < old < |V|\)，则出现 Gap。
当检测到 Gap 时，对所有高度在 \((old, |V|)\) 的节点，将其高度设为 \(|V|\) 或 \(|V|+1\)（不同实现有差异，目的是让它们能将流退回源点）。
这些节点之后会被 Relabel 到更高高度，最终将超额流推回源点。

为什么这样正确？

高度在 Gap 以上的节点，无法将流送到汇点（因为路径上需要严格递减的高度到 0 的汇点，但中间高度 missing）。
将它们提升到 \(|V|\) 以上，相当于标记为“与源点同侧”，允许将超额流沿残量边推回源点或重新分配。

4. 具体例子说明

考虑一个简单图：
\(V = \{s, a, b, t\}\)，边容量：
\((s,a):3, (s,b):2, (a,b):2, (a,t):2, (b,t):3\)。

初始化：

从 \(s\) 推送到 \(a\) 和 \(b\)，\(e(a)=3, e(b)=2\)，\(h(s)=4, h(a)=0, h(b)=0, h(t)=0\)。
此时 \(\text{count}[0]=3\)（a, b, t），\(\text{count}[4]=1\)（s）。

算法进行若干 Push/Relabel 后，假设某时刻高度分布：
\(h(a)=2, h(b)=1, h(t)=0, h(s)=4\)，且 \(\text{count}[1]=1, \text{count}[2]=1, \text{count}[0]=1, \text{count}[4]=1\)。

现在对某个节点 Relabel 后，若 \(\text{count}[1]\) 变为 0，则高度 1 出现 Gap。
检查发现存在节点高度 \(2\)（a），高度在 \((1,4)\) 之间，则将所有高度 \(>1\) 且 \(<4\) 的节点（即高度 2 的节点 a）的高度设为 4。
之后 a 的超额流可以推回 s 或流向 b。

5. 时间复杂度影响

不加 Gap 优化时，Push-Relabel 的复杂度为 \(O(V^2 \sqrt{E})\)（用最高标号优先选择节点）。
Gap Relabeling 可保证某些节点快速提升高度，减少 Relabel 总次数，在理论上不改变最坏复杂度，但在实际中显著加速。

6. 算法总结步骤

初始化：
- 对 \(s\) 的每条出边推送饱和流，更新超额流。
- 设 \(h(s)=|V|\)，其他节点 \(h(u)=0\)。
- 初始化 \(\text{count}[|V|]=1\)，\(\text{count}[0]=|V|-1\)。
选择有超额流的节点（非 \(s, t\)），尝试 Push。
若无法 Push 则 Relabel 该节点，更新 \(\text{count}\) 数组。
如果 Relabel 导致 \(\text{count}[old]=0\) 且 \(0，执行 Gap 优化：
- 遍历所有节点，若 \(old < h(u) < |V|\)，设 \(h(u)=|V|+1\)，更新 \(\text{count}\)。
重复直到除 \(s, t\) 外无超额流节点。
最终从 \(s\) 发出的总推送量减去回流到 \(s\) 的流量即为最大流。

这样，我们结合了 Gap Relabeling 优化，加速了经典的 Push-Relabel 最大流算法。

最大流问题（Push-Relabel 算法的 Gap Relabeling 优化）题目描述我们有一个有向图 \( G = (V, E) \)，每条边有容量 \( c(u,v) \ge 0 \)，指定源点 \( s \) 和汇点 \( t \)。目标是找到从 \( s \) 到 \( t \) 的最大流。 Push-Relabel 算法是求解最大流的经典方法之一，时间复杂度可达 \( O(V^2 \sqrt{E}) \) 或 \( O(V^3) \)，但它可以通过多种启发式优化来提升性能。其中 Gap Relabeling 是一种优化策略，可以在某些情况下减少不必要的操作，从而加速算法。解题步骤 1. Push-Relabel 算法回顾（不包含 Gap 优化） Push-Relabel 算法不维持流的守恒性（除了源和汇），而是维护：超额流 \( e(u) \)：进入节点 \( u \) 的流量多于离开的流量时，\( e(u) > 0 \)。高度 \( h(u) \)：每个节点有一个整数高度，满足： \( h(s) = |V| \)，\( h(t) = 0 \)（初始化时）。对于残量边 \( (u,v) \)，有 \( h(u) \le h(v) + 1 \)（高度约束）。算法重复执行两种基本操作： Push(u, v) ：如果 \( e(u) > 0 \)，残量边 \( (u,v) \) 的残量容量 \( r(u,v) > 0 \)，且 \( h(u) = h(v) + 1 \)。推送的流量 \( \Delta = \min(e(u), r(u,v)) \)。更新 \( e(u) \)、\( e(v) \)、残量容量。 Relabel(u) ：如果 \( e(u) > 0 \)，且对所有残量边 \( (u,v) \) 有 \( h(u) \le h(v) \)（无法直接推送）。将 \( h(u) \) 设为 \( \min\{ h(v) \mid (u,v) \text{ 是残量边} \} + 1 \)。初始化时，从 \( s \) 向所有邻居推送尽可能多的流量（使其饱和），并设置 \( h(s) = |V| \)，其他节点高度为 0。 2. Gap Relabeling 的动机观察高度引理：在算法运行中，对于任意高度 \( k \)，高度为 \( k \) 的节点数量不会变为 0 后再重新出现新的高度为 \( k \) 的节点，除非存在一个“间隙”。但如果在某个时刻，没有节点具有高度 \( m \) ，而存在节点高度 \( > m \) 且 \( < |V| \)，则这些节点无法将流送到汇点（因为高度差约束无法满足），可以直接将其高度提升到 \( |V|+1 \)，从而让超额流快速退回源点，减少无效操作。定义 Gap ：设高度标签范围是 \( 0 \) 到 \( 2|V|-1 \)（实际可达高度不超过 \( 2|V|-1 \)）。如果高度 \( k \) 没有节点，且存在节点高度在 \( (k, |V|] \) 之间，则称出现一个 Gap 。 3. Gap Relabeling 优化步骤在 Push-Relabel 算法中，维护一个数组 \( \text{count}[ k ] \) 记录当前高度为 \( k \) 的节点数量。当执行 Relabel(u) 时：设旧高度 \( old = h(u) \)。将 \( h(u) \) 提升到新高度 \( new \)。更新 \( \text{count}[ old] \) 减 1，\( \text{count}[ new ] \) 加 1。如果 \( \text{count}[ old] \) 变为 0，且 \( 0 < old < |V| \)，则出现 Gap。当检测到 Gap 时，对所有高度在 \( (old, |V|) \) 的节点，将其高度设为 \( |V| \) 或 \( |V|+1 \)（不同实现有差异，目的是让它们能将流退回源点）。这些节点之后会被 Relabel 到更高高度，最终将超额流推回源点。为什么这样正确？高度在 Gap 以上的节点，无法将流送到汇点（因为路径上需要严格递减的高度到 0 的汇点，但中间高度 missing）。将它们提升到 \( |V| \) 以上，相当于标记为“与源点同侧”，允许将超额流沿残量边推回源点或重新分配。 4. 具体例子说明考虑一个简单图： \( V = \{s, a, b, t\} \)，边容量： \( (s,a):3, (s,b):2, (a,b):2, (a,t):2, (b,t):3 \)。初始化：从 \( s \) 推送到 \( a \) 和 \( b \)，\( e(a)=3, e(b)=2 \)，\( h(s)=4, h(a)=0, h(b)=0, h(t)=0 \)。此时 \( \text{count}[ 0]=3 \)（a, b, t），\( \text{count}[ 4 ]=1 \)（s）。算法进行若干 Push/Relabel 后，假设某时刻高度分布： \( h(a)=2, h(b)=1, h(t)=0, h(s)=4 \)，且 \( \text{count}[ 1]=1, \text{count}[ 2]=1, \text{count}[ 0]=1, \text{count}[ 4 ]=1 \)。现在对某个节点 Relabel 后，若 \( \text{count}[ 1 ] \) 变为 0，则高度 1 出现 Gap。检查发现存在节点高度 \( 2 \)（a），高度在 \( (1,4) \) 之间，则将所有高度 \( >1 \) 且 \( <4 \) 的节点（即高度 2 的节点 a）的高度设为 4。之后 a 的超额流可以推回 s 或流向 b。 5. 时间复杂度影响不加 Gap 优化时，Push-Relabel 的复杂度为 \( O(V^2 \sqrt{E}) \)（用最高标号优先选择节点）。 Gap Relabeling 可保证某些节点快速提升高度，减少 Relabel 总次数，在理论上不改变最坏复杂度，但在实际中显著加速。 6. 算法总结步骤初始化：对 \( s \) 的每条出边推送饱和流，更新超额流。设 \( h(s)=|V| \)，其他节点 \( h(u)=0 \)。初始化 \( \text{count}[ |V|]=1 \)，\( \text{count}[ 0 ]=|V|-1 \)。选择有超额流的节点（非 \( s, t \)），尝试 Push。若无法 Push 则 Relabel 该节点，更新 \( \text{count} \) 数组。如果 Relabel 导致 \( \text{count}[ old]=0 \) 且 \( 0<old <|V| \)，执行 Gap 优化：遍历所有节点，若 \( old < h(u) < |V| \)，设 \( h(u)=|V|+1 \)，更新 \( \text{count} \)。重复直到除 \( s, t \) 外无超额流节点。最终从 \( s \) 发出的总推送量减去回流到 \( s \) 的流量即为最大流。这样，我们结合了 Gap Relabeling 优化，加速了经典的 Push-Relabel 最大流算法。