xxx 最大流问题（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）队列管理活跃节点（即溢出节点），通过局部操作（推送和重标记）逐步将流从源点推向汇点。 解题过程 基本概念 预流（Preflow） ：允许节点暂时存储超额流（excess flow），即流入量大于流出量。 高度函数（Height Function） ：为每个节点分配一个高度值，流只能从高节点推向低节点。 活跃节点（Active Node） ：除源点和汇点外，超额流 \( e(u) > 0 \) 的节点。 初始化 设置所有节点的高度 \( h(u) = 0 \)，超额流 \( e(u) = 0 \)。 将源点 \( s \) 的高度设为 \( |V| \)（节点总数）。 对 \( s \) 的所有出边进行饱和推送（推送流量 = 边容量），使相邻节点获得超额流，并将这些节点加入 FIFO 队列。 主循环（FIFO 队列处理） 当队列非空时： 取出队首节点 \( u \)。 尝试将 \( u \) 的超额流推送给高度更低的邻居节点： 推送操作 ：若边 \( (u, v) \) 有剩余容量且 \( h(u) = h(v) + 1 \)，则推送流量 \( \Delta = \min(e(u), c(u, v)) \)。 若 \( v \) 不是 \( s \) 或 \( t \) 且因推送变为活跃节点，则将其加入队列。 若 \( u \) 仍有超额流且无法推送，则执行 重标记操作 ：将 \( h(u) \) 设为 \( \min\{h(v) + 1 \mid (u, v) 有剩余容量\} \)。 若重标记后 \( u \) 仍活跃，将其重新加入队列尾部。 终止条件 当队列为空时，所有超额流已传递到汇点或流回源点，最终汇点的流量即为最大流。 示例说明 考虑一个简单图： 边容量：\( (s, a): 3, (s, b): 2, (a, b): 2, (a, t): 2, (b, t): 3 \)。 初始化后，\( s \) 推流到 \( a \) 和 \( b \)，队列为 \( [ a, b ] \)。 处理 \( a \)：推流到 \( b \)（若 \( h(a) > h(b) \)）和 \( t \)，若仍溢出则重标记高度。 重复过程直至队列空，最终得到最大流为 4。 关键点 FIFO 队列确保活跃节点按顺序处理，避免饥饿现象。 时间复杂度为 \( O(|V|^3) \)，但实际效率较高。