最大流问题（Push-Relabel算法） 题目描述 给定一个有向图 \( G = (V, E) \)，每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \)。指定源点 \( s \) 和汇点 \( t \)，求从 \( s \) 到 \( t \) 的最大流量。Push-Relabel算法通过维护每个顶点的 高度（height） 和 超额流（excess flow） 来逐步将流量推向汇点，最终达到最大流。 解题步骤 初始化 设置高度函数 \( h: V \to \mathbb{Z} \)，初始时 \( h(s) = |V| \)，其他顶点 \( h(v) = 0 \)。 设置超额流 \( e: V \to \mathbb{R} \)，初始时 \( e(v) = 0 \)。 初始化预流（preflow）：从 \( s \) 出发的边满流，即对每条边 \( (s, v) \)，推送流量 \( f(s, v) = c(s, v) \)，并更新 \( e(v) = c(s, v) \)，\( e(s) \) 相应减少。 算法核心操作 Push操作（推送流） ： 若顶点 \( u \) 有超额流（\( e(u) > 0 \)），且存在边 \( (u, v) \) 满足 剩余容量 \( c_ f(u, v) > 0 \) 且 \( h(u) = h(v) + 1 \) ，则推送流量 \( \Delta = \min(e(u), c_ f(u, v)) \) 到 \( v \)。 更新流量：\( f(u, v) += \Delta \)，\( f(v, u) -= \Delta \)。 更新超额流：\( e(u) -= \Delta \)，\( e(v) += \Delta \)。 Relabel操作（重标记高度） ： 若 \( u \) 有超额流，但无法推送（所有邻边 \( h(v) \geq h(u) \)），则抬高 \( u \) 的高度： \( h(u) = 1 + \min\{ h(v) \mid (u, v) \in E_ f \} \)，其中 \( E_ f \) 是剩余图中的边。 算法流程 不断选择有超额流的顶点（除 \( s \) 和 \( t \) 外），尝试Push或Relabel。 常用策略：使用队列维护有超额流的顶点，或按顺序处理（如FIFO）。 终止条件：所有顶点（除 \( s \) 和 \( t \) ）的超额流为0，此时流函数 \( f \) 即为最大流。 正确性关键 高度差限制保证了流不会形成环，且最终 \( s \) 和 \( t \) 的高度差 \( h(s) - h(t) \geq |V| \) 时，剩余图中无增广路。 复杂度：通用Push-Relabel为 \( O(V^2 E) \)，优化后（如最高标号法）可至 \( O(V^2 \sqrt{E}) \)。 示例说明 假设图有顶点 \( \{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 \)：Push到 \( t \)（流量2，剩余容量0），剩余超额流1；尝试Push到 \( b \)（因 \( h(a)=0 \), \( h(b)=0 \) 不满足高度差1，需先Relabel：\( h(a)=1 \)）。 继续推送直至所有超额流归零，得到最大流。