最大流问题的重标记与前移算法（Relabel-to-Front Algorithm） 题目描述 给定一个流网络，包含源点 s 和汇点 t，以及 n 个顶点、m 条有向边，每条边有容量。要求计算从 s 到 t 的最大流。你将实现一种高效的 push-relabel 算法变体——Relabel-to-Front 算法，时间复杂度为 O(n³)。 解题过程 1. 前置知识：Push-Relabel 框架 Push-Relabel 算法是最大流问题的另一类解法，不维护流的守恒性，而是维护每个顶点的“高度”和“超额流”。核心操作： 推流（Push） ：将超额流从当前顶点推向高度较低的邻居。 重标记（Relabel） ：若当前顶点有超额流但无法推给任何较低邻居，则抬高其高度。 Relabel-to-Front 算法在此基础上，通过一个“顶点列表”的顺序处理，将复杂度优化到 O(n³)。 2. 算法数据结构 容量 c(u, v)：边 (u, v) 的容量。 流量 f(u, v)：当前流。 超额流 e(u)：顶点 u 的净流入超出其流出部分（源点、汇点除外）。 高度 h(u)：顶点 u 的高度，h(s)=n，h(t)=0，初始时其他顶点高度为 0。 邻接表 N(u)：记录所有邻居（包括反向边）。 当前弧 current[ u ]：记录下一次要检查的邻居在 N(u) 中的位置，用于跳过已处理的边。 3. 算法初始化 初始化所有流量 f(u, v) = 0。 对源点 s 的每条出边 (s, v)，执行 f(s, v) = c(s, v)，e(v) = c(s, v)，e(s) 减去相应值。 初始化 h(s) = n，其他顶点高度 h(u) = 0。 构建顶点列表 L：包含所有顶点（除 s 和 t），顺序任意。 4. 算法主循环 维护一个指针指向 L 中的当前顶点 u。重复以下步骤直到处理完 L 中所有顶点： 记 u 的原始高度为 old_ height。 当 e(u) > 0 时，尝试推流或重标记： a. 从 current[ u ] 开始扫描邻接表 N(u)，对每条边 (u, v)： 若 h(u) == h(v) + 1 且边 (u, v) 有剩余容量（c(u,v)-f(u,v) > 0），则执行 push(u, v)。 推送量 Δ = min(e(u), 剩余容量)。 更新 f(u, v) 和 e(u)、e(v)，若 v 不是 s 或 t 且 e(v) 刚变为正，则将 v 移到 L 的头部。 b. 若扫描完所有邻居后 e(u) > 0，则执行 relabel(u)： 将 h(u) 设为 1 + min{ h(v) | (u,v) 有剩余容量 }。 c. 若重标记后 h(u) 增加，则将 u 移到 L 的头部，重置指针指向 L 的新头部。 若 e(u) 变为 0 或 u 的高度未变，则移动指针到 L 中的下一个顶点。 5. 推流与重标记的细节 Push 操作需更新正向边和反向边流量。 Relabel 操作需检查所有邻接边，找出有剩余容量的邻居的最小高度。 6. 正确性保证 高度引理：始终有 h(u) ≤ h(v) + 1 对于任意有剩余容量的边 (u, v)。 高度函数确保无环，且最终汇点高度不变，源点高度始终为 n。 当除 s、t 外无超额流时，流即为最大流。 7. 时间复杂度分析 重标记次数最多 2n² 次（每个顶点高度不超过 2n）。 饱和推流（使边满）最多 O(nm) 次。 非饱和推流最多 O(n³) 次（每次推流使当前顶点在 L 中前移）。 总复杂度 O(n³)。 8. 举例说明 考虑一个简单网络：s→a (cap=3)，s→b (cap=2)，a→t (cap=2)，a→b (cap=1)，b→t (cap=3)。 初始化：从 s 推流到 a、b，e(a)=3, e(b)=2，高度 h(s)=4, 其他为 0。 处理顶点 a：推 2 到 t，推 1 到 b（因 h(a)=0 不高于 h(b)，需先重标记 a 为 1），更新超额流。 依次处理顶点，直到所有 e(u)=0，得到最大流 4。 9. 总结 Relabel-to-Front 是 push-relabel 算法的高效实现，通过维护顶点列表的顺序，避免全局扫描，将复杂度优化到 O(n³)，适合稠密图的最大流计算。掌握其高度管理、推流条件与列表更新是关键。