xxx 最大流问题（Push-Relabel 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。图中有一个源点 \( s \) 和一个汇点 \( t \)。Push-Relabel 算法通过局部操作（推送流量和重标高度）来逐步将流量从源点推向汇点，最终求出从 \( s \) 到 \( t \) 的最大流。与增广路径类算法（如 Ford-Fulkerson）不同，Push-Relabel 不维护合法的流结构，而是允许暂时违反流量守恒约束，通过调整高度函数最终收敛到最大流。 解题过程 1. 基本概念 预流（Preflow） ：允许节点的流入量大于等于流出量（即超额流量 \( e(u) \geq 0 \)），仅源点 \( s \) 和汇点 \( t \) 可以违反流量守恒。 高度函数（Height Function） ：为每个节点 \( u \) 分配一个整数高度 \( h(u) \)，满足 \( h(s) = |V| \)，\( h(t) = 0 \)，且对于残量边 \( (u, v) \) 有 \( h(u) \leq h(v) + 1 \)。 残量网络（Residual Network） ：定义与 Ford-Fulkerson 相同，残量容量 \( r(u, v) = c(u, v) - f(u, v) + f(v, u) \)。 3. 核心操作 推送（Push） ：对于超额节点 \( u \)（即 \( e(u) > 0 \)），尝试将超额流量沿残量边 \( (u, v) \) 推送到相邻的较低节点（要求 \( h(u) = h(v) + 1 \) 且 \( r(u, v) > 0 \)）。推送量为 \( \Delta = \min(e(u), r(u, v)) \)。 重标高度（Relabel） ：若当前节点 \( u \) 有超额流量，但无合法邻接点可推送（所有残量边满足 \( h(u) \leq h(v) \)），则将 \( h(u) \) 提升到 \( \min\{h(v) + 1 \mid (u, v) \in E_ f\} \)。 4. 算法步骤 初始化 ： 设置高度：\( h(s) = |V| \)，\( h(u) = 0 \)（\( u \neq s \)）。 初始化流：对 \( s \) 的所有出边推送满容量（即 \( f(s, v) = c(s, v) \)），使邻接点获得超额流量。 主循环 ： 选择任意超额节点 \( u \neq t \)。 若存在邻接点 \( v \) 满足 \( h(u) = h(v) + 1 \) 且 \( r(u, v) > 0 \)，则执行 Push 操作。 否则，执行 Relabel 操作提升 \( h(u) \)。 终止条件 ：当除 \( s \) 和 \( t \) 外无超额节点时，算法结束。此时流量守恒，得到最大流。 5. 实例演示 考虑一个简单图： 节点 \( V = \{s, a, b, t\} \)，边容量： \( (s, a): 3 \), \( (s, b): 2 \), \( (a, b): 1 \), \( (a, t): 2 \), \( (b, t): 3 \)。 步骤 ： 初始化：\( h(s) = 4 \)，其他节点高度为 0。从 \( s \) 推送到 \( a \)（流量 3）和 \( b \)（流量 2），此时 \( e(a)=3, e(b)=2 \)。 选择 \( a \)：发现 \( h(a)=0 \)，邻接点 \( b \) 和 \( t \) 高度均为 0，不满足推送条件，故重标 \( h(a) = 1 \)。 从 \( a \) 推送到 \( b \)（残量边 \( (a, b) \) 容量 1）：推送流量 1，更新 \( e(a)=2, e(b)=3 \)。 从 \( a \) 推送到 \( t \)（条件满足）：推送流量 2，\( e(a)=0, e(t)=2 \)。 选择 \( b \)：重标 \( h(b)=1 \) 后，推送到 \( t \) 流量 3，\( e(b)=0, e(t)=5 \)。 无超额节点，结束。最大流为 5。 6. 优化与复杂度 队列实现 ：总是处理最高超额节点（最高标号法），复杂度 \( O(|V|^2\sqrt{|E|}) \)。 间隙启发式 ：若某高度无节点，可标记更高节点为不可达，加速收敛。 7. 关键点 Push-Relabel 通过高度差控制流量方向，避免反复增广。 重标操作确保流量不会形成死循环，最终所有流量必到达 \( t \)。