最大流问题（Relabel-to-Front 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( (u, v) \) 有一个非负容量 \( c(u, v) \)，指定一个源点 \( s \) 和一个汇点 \( t \)，求从 \( s \) 到 \( t \) 的最大流。 Relabel-to-Front 是 Push-Relabel 算法的一种高效实现，它通过维护一个顶点列表，在列表上依次对每个顶点进行“推送”和“重标记”操作，从而找到最大流。其时间复杂度为 \( O(V^3) \)，在实际稀疏图中通常表现出色。该算法是许多最大流算法竞赛和高效库实现的基础。 解题过程 Relabel-to-Front 是 Push-Relabel 算法的一种具体实现，核心思想是模拟水流在高度差下流动，通过“推送”超额流到相邻点，并在必要时“重标记”顶点高度，最终使除源点和汇点外所有顶点超额流为零，得到最大流。以下是详细步骤： 1. 核心概念准备 预流（Preflow） ：对每条边 \( (u, v) \)，满足 \( 0 \le f(u, v) \le c(u, v) \)（容量限制），且对所有顶点 \( u \in V \setminus \{s, t\} \) 满足 超额流 \( e(u) = \sum_ {v \in V} f(v, u) - \sum_ {v \in V} f(u, v) \ge 0 \)（即进入流量不少于流出流量）。源点 \( s \) 可有无限制流出，汇点 \( t \) 可有无限制流入。 高度函数（Height/Label） ：每个顶点 \( u \) 有整数高度 \( h(u) \)。初始化 \( h(s) = |V| \)，\( h(t) = 0 \)，其他顶点 \( h(u) = 0 \)。推送操作只允许从较高顶点向较低顶点推流。 超额流（Excess Flow） ：顶点 \( u \) 的超额流 \( e(u) \) 如上定义。若 \( e(u) > 0 \)，称 \( u \) 为活跃顶点（active vertex）。 残余图（Residual Graph） ：与常规最大流算法类似，定义残余容量 \( c_ f(u, v) = c(u, v) - f(u, v) + f(v, u) \)。注意反向边的容量表示可取消的流。 2. 算法基本操作 Relabel-to-Front 依赖两个基本操作： 推送（Push） ：对活跃顶点 \( u \) 和其邻居 \( v \)，若 \( h(u) = h(v) + 1 \) 且 \( c_ f(u, v) > 0 \)，则可推送流量 \( \Delta = \min(e(u), c_ f(u, v)) \)。更新 \( f(u, v) \), \( f(v, u) \), \( e(u) \), \( e(v) \) 相应变化。若推送后 \( c_ f(u, v) = 0 \)，称为饱和推送；否则为非饱和推送。 重标记（Relabel） ：对活跃顶点 \( u \)，若不存在 \( v \) 满足 \( h(u) = h(v) + 1 \) 且 \( c_ f(u, v) > 0 \)，则将 \( h(u) \) 增加为 \( \min\{h(v) : c_ f(u, v) > 0\} + 1 \)。这使后续推送成为可能。 3. Relabel-to-Front 的特殊结构 顶点列表 L ：将所有顶点（除 \( s \) 和 \( t \) ）按任意顺序放入列表 L。算法遍历 L，对每个顶点执行“释放操作”（discharge），直到 L 被完全处理。 释放操作（Discharge） ：对当前顶点 \( u \)： a. 当 \( e(u) > 0 \) 时，遍历其邻居列表（在残余图中）。 b. 对每个邻居 \( v \)，若 \( h(u) = h(v) + 1 \) 且 \( c_ f(u, v) > 0 \)，则执行推送。 c. 若遍历完邻居后 \( e(u) > 0 \)，则对 \( u \) 执行重标记，并重置邻居指针到起始位置（以便重新检查）。 邻居列表 N[ u] ：对每个顶点 \( u \)，预先存储所有可能邻居（包括残余图中的反向边）。顺序任意，但在重标记后需重置遍历指针。 4. 算法步骤 初始化 ： 设 \( f(u, v) = 0 \) 对所有边。 设 \( h(s) = |V| \)，\( h(u) = 0 \) 对 \( u \neq s \)。 对每条从 \( s \) 出发的边 \( (s, v) \)，执行饱和推送：\( f(s, v) = c(s, v) \)，\( e(v) = c(s, v) \)，\( e(s) \) 减少相应值。 构造列表 L，包含所有 \( u \in V \setminus \{s, t\} \)。 主循环 ： 初始化当前指针指向 L 的头部。 当指针未到达 L 尾部时： a. 令 \( u \) 为当前指针所指顶点。 b. 记录 \( u \) 的旧高度 \( old\_height = h(u) \)。 c. 对 \( u \) 执行释放操作（不断推送/重标记直到 \( e(u) = 0 \)）。 d. 若释放过程中 \( h(u) \) 增加了（即重标记过），则将 \( u \) 移动到 L 的头部，并重置指针到 L 头部。 e. 否则，指针移动到 L 中下一个顶点。 结束 ：当 L 遍历完成（所有顶点超额流为零），算法终止。此时 \( f \) 即为最大流。 5. 正确性与复杂度 正确性 ：算法是 Push-Relabel 的一种实现，保持预流性质，最终无活跃顶点时即为最大流（高度函数保证无残余路径）。 时间复杂度 ：每个顶点重标记次数不超过 \( 2|V| \)（高度不超过 \( 2|V| \)），总推送操作 \( O(V^2 E) \)，但 Relabel-to-Front 通过顶点列表管理减少了非饱和推送，达到 \( O(V^3) \)。实际中常比此界快。 空间复杂度 ：\( O(V^2) \) 存储容量矩阵，或 \( O(V + E) \) 用邻接表。 6. 例子说明 考虑一个简单有向图：顶点 \( s, a, b, t \)，边容量：\( s \to a: 3 \), \( s \to b: 2 \), \( a \to b: 1 \), \( a \to t: 2 \), \( b \to t: 3 \)。 初始化：\( h(s)=4 \), 其他高度 0，推送 \( s \to a: 3 \), \( s \to b: 2 \)，则 \( e(a)=3, e(b)=2 \)。L = [ a, b ]。 处理 a：邻居包括 b, t, s。对 b 不满足高度差（0 vs 0），对 t 满足 \( h(a)=0, h(t)=0 \) 不满足。重标记 a 高度为 1（因残余边 a→t 容量 2，t 高度 0）。将 a 移到 L 头部，L = [ a, b ]，重置指针。 再处理 a：对 t 满足 \( h(a)=1, h(t)=0 \)，推送 2 到 t（饱和），\( e(a)=1 \)。对 b 满足 \( h(a)=1, h(b)=0 \)，推送 1 到 b（饱和），\( e(a)=0 \)。完成释放 a。 处理 b：邻居包括 a, t, s。e(b)=2（初始）+1（来自 a）=3。对 t 满足 \( h(b)=0, h(t)=0 \) 不满足，对 a 满足 \( h(b)=0, h(a)=1 \) 不满足。重标记 b 为 1（因 b→t 容量 3，t 高度 0）。将 b 移到 L 头部，L = [ b, a ]，重置指针。 处理 b：对 t 满足 \( h(b)=1, h(t)=0 \)，推送 3 到 t（饱和），\( e(b)=0 \)。完成释放 b。 处理 a：e(a)=0，跳过。算法结束。 最大流为 5（s→a→t:2, s→a→b→t:1, s→b→t:2）。 7. 关键优化与注意事项 邻居列表顺序影响效率，但最坏复杂度不变。 重标记后移动顶点到列表头部，类似 LRU 策略，保证活跃顶点尽快处理。 算法结束时，最小割可通过高度函数得到：所有高度 \( \ge |V| \) 的顶点在源点侧。 Relabel-to-Front 结合了高度差推送与列表管理，避免了递归或广度搜索，是最大流问题的高效实践算法之一。