最大流问题的 FIFO 顶点高度重标算法（FIFO Push-Relabel with Gap Relabeling 优化）
字数 3492 2025-12-12 05:24:11

最大流问题的 FIFO 顶点高度重标算法（FIFO Push-Relabel with Gap Relabeling 优化）

题目描述

给定一个有向图 \(G=(V,E)\)，其中每条边 \((u,v)\in E\) 有一个非负整数容量 \(c(u,v) \ge 0\)。指定一个源点 \(s\) 和一个汇点 \(t\)。目标是计算从 \(s\) 到 \(t\) 的最大流（Maximum Flow），即一种分配在每条边上的非负流值 \(f(u,v)\)，满足容量限制（\(f(u,v) \le c(u,v)\)）、流量守恒（除 \(s\) 和 \(t\) 外，每个顶点的流入等于流出），且从 \(s\) 流出的总流量最大。
本题目要求实现 Push-Relabel 算法的一种高效变体：FIFO 顶点高度重标算法（FIFO Push-Relabel），并加入 Gap Relabeling 优化以加速收敛。

背景与核心思想

Push-Relabel 算法是最大流问题的主流算法之一，它不维护流的“可行流”属性（即允许暂时违反流量守恒），而是通过两个基本操作推进计算：

  1. Push（推流）：如果某个顶点 \(u\) 有多余流量（excess flow）且存在邻居 \(v\) 满足 \(h(u) = h(v) + 1\) 且边 \((u,v)\) 有剩余容量，则尽可能将多余流量推送到 \(v\)。
  2. Relabel（重标高度）：若顶点 \(u\) 有多余流量，但无法推流（因为没有满足高度条件的邻居有剩余容量），则将其高度 \(h(u)\) 提高到比其最低的、有剩余容量的邻居高度高 1。

FIFO Push-Relabel 使用队列管理有多余流量的顶点，按先进先出顺序处理，确保算法结构清晰且易于实现。Gap Relabeling 则是一种优化：如果某个高度值 \(k\) 在高度数组中不再有任何顶点，则所有高度大于 \(k\) 且小于 \(|V|\) 的顶点都无法将流量推送到汇点，可直接将其高度设为 \(|V|+1\)，提前终止其活动状态。

解题步骤详解

步骤 1：初始化

  • 令 \(n = |V|\)。创建高度数组 \(height[0..n-1]\) 和多余流量数组 \(excess[0..n-1]\)，初始全为 0。
  • 创建残量图（邻接表或矩阵），记录每条边的剩余容量 \(r(u,v) = c(u,v)\)，反向边 \(r(v,u) = 0\)。
  • 对源点 \(s\) 进行初始化预流（preflow）：
    • 设置 \(height[s] = n\)（源点始终在最高处）。
    • 对每条从 \(s\) 出发的边 \((s,v)\)，执行 Push 操作：推送 \(c(s,v)\) 的流量到 \(v\)，即设置 \(r(s,v)=0\)，\(r(v,s)=c(s,v)\)，并增加 \(excess[v]\)。
  • 将所有 \(excess[v]>0\) 且 \(v \notin \{s,t\}\) 的顶点加入 FIFO 队列 \(Q\)。

步骤 2：主循环（处理队列中的顶点）

当队列 \(Q\) 非空时：

  1. 取出队首顶点 \(u\)。
  2. 尝试对 \(u\) 执行 Push 操作：
    • 遍历 \(u\) 的所有邻接顶点 \(v\)（在残量图中）。
    • 如果 \(height[u] = height[v] + 1\) 且 \(r(u,v) > 0\)，则可以进行推流。
    • 推送量 \(\Delta = \min(excess[u], r(u,v))\)。
    • 更新：\(r(u,v) \leftarrow r(u,v) - \Delta\)，\(r(v,u) \leftarrow r(v,u) + \Delta\)。
    • 更新多余流量：\(excess[u] \leftarrow excess[u] - \Delta\)，\(excess[v] \leftarrow excess[v] + \Delta\)。
    • 如果 \(v\) 不是 \(s\) 或 \(t\)，且 \(v\) 原本 \(excess[v]=0\) 而现在 \(\Delta>0\)，则将 \(v\) 加入队尾（因为 \(v\) 新出现了多余流量）。
    • 如果 \(excess[u] = 0\)，则跳出循环（\(u\) 的多余流量已处理完）。
  3. 如果遍历完所有邻居后 \(excess[u] > 0\)，说明 \(u\) 仍有多余流量但无法推流，则执行 Relabel 操作：
    • 找到 \(u\) 的邻居中满足 \(r(u,v) > 0\) 的最小高度 \(min\_height\)。
    • 设置 \(height[u] = min\_height + 1\)。
  4. 执行 Gap Relabeling 优化：
    • 维护一个高度计数数组 \(cnt[0..2n-1]\)，记录当前每个高度值上有多少顶点。
    • 当 Relabel 操作使某个高度 \(k\) 的计数变为 0 时，说明高度 \(k\) 出现“间隙”（gap）。
    • 遍历所有顶点，若顶点 \(w\) 的高度 \(h(w) > k\) 且 \(h(w) < n\)，则设置 \(height[w] = n+1\)（使其直接失效）。
  5. 如果 \(u\) 在 Push 或 Relabel 后仍有 \(excess[u] > 0\)，则将 \(u\) 重新加入队尾（因为它还需继续处理）。

步骤 3：终止与输出

  • 当队列为空时，算法终止。此时汇点 \(t\) 的多余流量（即 \(excess[t]\)）就是最大流值。也可通过源点 \(s\) 发出的总流量减去流回 \(s\) 的流量计算。
  • 最终最大流值即为所求，每条边 \((u,v)\) 的流量为初始容量减去残量容量：\(f(u,v) = c(u,v) - r(u,v)\)。

关键点说明

  • 高度函数：保证源点高度固定为 \(n\)，汇点高度始终为 0。高度差为 1 时才能推流，防止形成循环。
  • FIFO 队列：确保每个活动顶点被轮流处理，避免某些顶点“饿死”。
  • Gap Relabeling：当高度 \(k\) 没有顶点时，高于 \(k\) 的顶点无法将流量推到更低高度（因为高度必须连续递减到汇点），因此可提前将其标记为无效，减少后续操作。
  • 复杂度：基本 FIFO Push-Relabel 的时间复杂度为 \(O(V^3)\)，加入 Gap Relabeling 后实践中接近 \(O(V^{2.5})\)，优于 Edmonds-Karp 的 \(O(VE^2)\)。

举例说明

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

  1. 初始化：\(height[s]=3\)，\(height[a]=0\)，\(height[t]=0\)。推流 \(s \to a:3\)，\(excess[a]=3\)；推流 \(s \to t:1\)，\(excess[t]=1\)。队列 \(Q=[a]\)。
  2. 处理 \(a\)：尝试推流到 \(t\)（因为 \(height[a]=0\)，不满足 \(height[a]=height[t]+1\)，无法推流），因此重标 \(a\)：邻居 \(t\) 有剩余容量 2，最小高度为 0，设置 \(height[a]=1\)。重新入队。
  3. 再次处理 \(a\)：现在 \(height[a]=1\)，满足 \(height[a]=height[t]+1\)，推送 \(\min(excess[a]=3, r(a,t)=2)=2\) 到 \(t\)。更新后 \(excess[a]=1\)，\(excess[t]=3\)。重新入队。
  4. 处理 \(a\)：无法再推流到 \(t\)（剩余容量为 0），重标高度：邻居中无剩余容量的可达点，设置 \(height[a]=7\)（通过 Gap 优化）。此时 \(a\) 仍有多余流量但无法推送。
  5. 队列为空。最大流为 \(excess[t]=3\)，对应边流量：\(f(s,a)=2\)，\(f(a,t)=2\)，\(f(s,t)=1\)。

通过此例可见，算法通过不断调整高度和推送，最终将所有可推送流量送达汇点，而 Gap 优化加速了无效顶点的淘汰。

最大流问题的 FIFO 顶点高度重标算法（FIFO Push-Relabel with Gap Relabeling 优化） 题目描述 给定一个有向图 \(G=(V,E)\)，其中每条边 \((u,v)\in E\) 有一个非负整数容量 \(c(u,v) \ge 0\)。指定一个源点 \(s\) 和一个汇点 \(t\)。目标是计算从 \(s\) 到 \(t\) 的最大流（Maximum Flow），即一种分配在每条边上的非负流值 \(f(u,v)\)，满足容量限制（\(f(u,v) \le c(u,v)\)）、流量守恒（除 \(s\) 和 \(t\) 外，每个顶点的流入等于流出），且从 \(s\) 流出的总流量最大。 本题目要求实现 Push-Relabel 算法的一种高效变体： FIFO 顶点高度重标算法（FIFO Push-Relabel） ，并加入 Gap Relabeling 优化以加速收敛。 背景与核心思想 Push-Relabel 算法是最大流问题的主流算法之一，它不维护流的“可行流”属性（即允许暂时违反流量守恒），而是通过两个基本操作推进计算： Push（推流） ：如果某个顶点 \(u\) 有多余流量（excess flow）且存在邻居 \(v\) 满足 \(h(u) = h(v) + 1\) 且边 \((u,v)\) 有剩余容量，则尽可能将多余流量推送到 \(v\)。 Relabel（重标高度） ：若顶点 \(u\) 有多余流量，但无法推流（因为没有满足高度条件的邻居有剩余容量），则将其高度 \(h(u)\) 提高到比其最低的、有剩余容量的邻居高度高 1。 FIFO Push-Relabel 使用队列管理有多余流量的顶点，按先进先出顺序处理，确保算法结构清晰且易于实现。Gap Relabeling 则是一种优化：如果某个高度值 \(k\) 在高度数组中不再有任何顶点，则所有高度大于 \(k\) 且小于 \(|V|\) 的顶点都无法将流量推送到汇点，可直接将其高度设为 \(|V|+1\)，提前终止其活动状态。 解题步骤详解 步骤 1：初始化 令 \(n = |V|\)。创建高度数组 \(height[ 0..n-1]\) 和多余流量数组 \(excess[ 0..n-1 ]\)，初始全为 0。 创建残量图（邻接表或矩阵），记录每条边的剩余容量 \(r(u,v) = c(u,v)\)，反向边 \(r(v,u) = 0\)。 对源点 \(s\) 进行 初始化预流 （preflow）： 设置 \(height[ s ] = n\)（源点始终在最高处）。 对每条从 \(s\) 出发的边 \((s,v)\)，执行 Push 操作：推送 \(c(s,v)\) 的流量到 \(v\)，即设置 \(r(s,v)=0\)，\(r(v,s)=c(s,v)\)，并增加 \(excess[ v ]\)。 将所有 \(excess[ v ]>0\) 且 \(v \notin \{s,t\}\) 的顶点加入 FIFO 队列 \(Q\)。 步骤 2：主循环（处理队列中的顶点） 当队列 \(Q\) 非空时： 取出队首顶点 \(u\)。 尝试对 \(u\) 执行 Push 操作： 遍历 \(u\) 的所有邻接顶点 \(v\)（在残量图中）。 如果 \(height[ u] = height[ v ] + 1\) 且 \(r(u,v) > 0\)，则可以进行推流。 推送量 \(\Delta = \min(excess[ u ], r(u,v))\)。 更新：\(r(u,v) \leftarrow r(u,v) - \Delta\)，\(r(v,u) \leftarrow r(v,u) + \Delta\)。 更新多余流量：\(excess[ u] \leftarrow excess[ u] - \Delta\)，\(excess[ v] \leftarrow excess[ v ] + \Delta\)。 如果 \(v\) 不是 \(s\) 或 \(t\)，且 \(v\) 原本 \(excess[ v ]=0\) 而现在 \(\Delta>0\)，则将 \(v\) 加入队尾（因为 \(v\) 新出现了多余流量）。 如果 \(excess[ u ] = 0\)，则跳出循环（\(u\) 的多余流量已处理完）。 如果遍历完所有邻居后 \(excess[ u] > 0\)，说明 \(u\) 仍有多余流量但无法推流，则执行 Relabel 操作： 找到 \(u\) 的邻居中满足 \(r(u,v) > 0\) 的最小高度 \(min\_height\)。 设置 \(height[ u ] = min\_height + 1\)。 执行 Gap Relabeling 优化： 维护一个高度计数数组 \(cnt[ 0..2n-1 ]\)，记录当前每个高度值上有多少顶点。 当 Relabel 操作使某个高度 \(k\) 的计数变为 0 时，说明高度 \(k\) 出现“间隙”（gap）。 遍历所有顶点，若顶点 \(w\) 的高度 \(h(w) > k\) 且 \(h(w) < n\)，则设置 \(height[ w ] = n+1\)（使其直接失效）。 如果 \(u\) 在 Push 或 Relabel 后仍有 \(excess[ u ] > 0\)，则将 \(u\) 重新加入队尾（因为它还需继续处理）。 步骤 3：终止与输出 当队列为空时，算法终止。此时汇点 \(t\) 的多余流量（即 \(excess[ t ]\)）就是最大流值。也可通过源点 \(s\) 发出的总流量减去流回 \(s\) 的流量计算。 最终最大流值即为所求，每条边 \((u,v)\) 的流量为初始容量减去残量容量：\(f(u,v) = c(u,v) - r(u,v)\)。 关键点说明 高度函数 ：保证源点高度固定为 \(n\)，汇点高度始终为 0。高度差为 1 时才能推流，防止形成循环。 FIFO 队列 ：确保每个活动顶点被轮流处理，避免某些顶点“饿死”。 Gap Relabeling ：当高度 \(k\) 没有顶点时，高于 \(k\) 的顶点无法将流量推到更低高度（因为高度必须连续递减到汇点），因此可提前将其标记为无效，减少后续操作。 复杂度 ：基本 FIFO Push-Relabel 的时间复杂度为 \(O(V^3)\)，加入 Gap Relabeling 后实践中接近 \(O(V^{2.5})\)，优于 Edmonds-Karp 的 \(O(VE^2)\)。 举例说明 考虑一个简单图：\(V=\{s,a,t\}\)，边 \((s,a):3\)，\((a,t):2\)，\((s,t):1\)。 初始化：\(height[ s]=3\)，\(height[ a]=0\)，\(height[ t]=0\)。推流 \(s \to a:3\)，\(excess[ a]=3\)；推流 \(s \to t:1\)，\(excess[ t]=1\)。队列 \(Q=[ a ]\)。 处理 \(a\)：尝试推流到 \(t\)（因为 \(height[ a]=0\)，不满足 \(height[ a]=height[ t]+1\)，无法推流），因此重标 \(a\)：邻居 \(t\) 有剩余容量 2，最小高度为 0，设置 \(height[ a ]=1\)。重新入队。 再次处理 \(a\)：现在 \(height[ a]=1\)，满足 \(height[ a]=height[ t]+1\)，推送 \(\min(excess[ a]=3, r(a,t)=2)=2\) 到 \(t\)。更新后 \(excess[ a]=1\)，\(excess[ t ]=3\)。重新入队。 处理 \(a\)：无法再推流到 \(t\)（剩余容量为 0），重标高度：邻居中无剩余容量的可达点，设置 \(height[ a ]=7\)（通过 Gap 优化）。此时 \(a\) 仍有多余流量但无法推送。 队列为空。最大流为 \(excess[ t ]=3\)，对应边流量：\(f(s,a)=2\)，\(f(a,t)=2\)，\(f(s,t)=1\)。 通过此例可见，算法通过不断调整高度和推送，最终将所有可推送流量送达汇点，而 Gap 优化加速了无效顶点的淘汰。