最大流问题（FIFO Push-Relabel算法） 题目描述 给定一个有向图 \( G = (V, E) \)，每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。指定源点 \( s \) 和汇点 \( t \)，要求计算从 \( s \) 到 \( t \) 的最大流。FIFO Push-Relabel 算法是 Push-Relabel 算法的一种高效实现，通过先进先出（FIFO）队列管理活跃节点（即存在超额流的节点），优化性能至 \( O(|V|^3) \)。 解题步骤 初始化 设置高度函数 \( h: V \to \mathbb{Z} \)：\( h(s) = |V| \)，其他节点 \( h(u) = 0 \)。 设置流函数 \( f: E \to \mathbb{R} \)：初始流量为 0。 计算初始超额流 \( e: V \to \mathbb{R} \)：对 \( s \) 的每条出边执行饱和推送（Push），使 \( e(s) = -\sum_ {v} f(s, v) \)，其他节点 \( e(u) = \sum_ {w} f(w, u) \)。 将除 \( s \) 和 \( t \) 外所有超额流 \( e(u) > 0 \) 的节点加入 FIFO 队列。 主循环（直到队列为空） 从队列头部取出节点 \( u \)。 若 \( e(u) > 0 \)（仍活跃），尝试推送流或重标记高度： 推送操作（Push） ： 对 \( u \) 的每条出边 \( (u, v) \)，若 \( h(u) = h(v) + 1 \) 且边有剩余容量 \( r(u, v) = c(u, v) - f(u, v) > 0 \)，则推送 \( \Delta = \min(e(u), r(u, v)) \) 的流： 更新 \( f(u, v) += \Delta \)，\( f(v, u) -= \Delta \)（反向边）。 更新超额流 \( e(u) -= \Delta \)，\( e(v) += \Delta \)。 若 \( v \neq s, t \) 且 \( e(v) \) 由 0 变为正，将 \( v \) 加入队列尾部。 重标记操作（Relabel） ： 若所有出边均无法推送（即不满足 \( h(u) > h(v) \) 且 \( r(u, v) > 0 \)），则重标记 \( u \) 的高度： \( h(u) = 1 + \min\{ h(v) \mid (u, v) \in E, r(u, v) > 0 \} \)。 重标记后，\( u \) 可能恢复推送条件，将其重新加入队列尾部。 若 \( e(u) > 0 \) 但无法立即推送（需等待后续操作），保留在队列中（算法设计会持续处理）。 终止与结果 当队列为空时，所有节点（除 \( s \) 和 \( t \)）的超额流均为 0。 最大流值为汇点 \( t \) 的流入量 \( \sum_ {v} f(v, t) \)，或源点 \( s \) 的流出量 \( \sum_ {v} f(s, v) \)。 关键点说明 FIFO 队列 ：确保活跃节点按进入顺序处理，避免饥饿现象。 高度函数 ：保证流只能推向更低高度的节点，防止循环。 复杂度 ：每节点重标记次数至多 \( 2|V| \) 次，总推送操作 \( O(|V|^2|E|) \)，FIFO 优化后达 \( O(|V|^3) \)。 通过以上步骤，FIFO Push-Relabel 算法高效解决了最大流问题，适用于稠密图或需高精度流的场景。