最大流问题（FIFO Push-Relabel算法）

最大流问题是在有向图中，从源点s到汇点t的最大流量传输问题。FIFO Push-Relabel算法是Push-Relabel算法的一种高效实现，它使用先进先出（FIFO）队列管理活跃节点，以优化性能。

题目描述
给定一个有向图G=(V,E)，每条边e有一个非负容量c(e)。源点s和汇点t。求从s到t的最大流量。

解题过程
Push-Relabel算法不维护流的守恒性，而是维护一个预流（允许节点暂时存储超额流量）和高度函数，通过两种操作（Push和Relabel）逐步将预流转化为最大流。FIFO版本使用队列来管理活跃节点（即超额流量大于0的非源非汇节点），确保按先进先出顺序处理。

1. 初始化

   • 设置高度函数h：h(s)=|V|，h(v)=0（v≠s）。
   • 设置预流f：对于s的所有出边(s,v)，f(s,v)=c(s,v)；其他边f=0。
   • 初始化超额流量e：e(s)=0，e(v)=f(s,v)（v与s相邻）。
   • 将s的所有邻居（若超额>0）加入FIFO队列。

2. 主循环（当队列非空）
   从队列头部取出一个节点u，尝试对其执行Push或Relabel操作，直到e(u)=0或无法操作。操作后，若其他节点变为活跃，则加入队列尾部。

   • Push操作（如果存在边(u,v)满足h(u)=h(v)+1且剩余容量>0）
     沿边(u,v)推送流量：
     Δ = min(e(u), c(u,v) - f(u,v))
     更新f(u,v) += Δ, f(v,u) -= Δ
     更新e(u) -= Δ, e(v) += Δ
     若v变为活跃（v≠s,t）且不在队列中，则加入队列。

   • Relabel操作（如果无法Push但e(u)>0）
     提升u的高度：h(u) = 1 + min{ h(v) | (u,v)有剩余容量 }
     此操作后，u可能具备Push条件。

3. 终止
   当队列为空时，算法结束。此时汇点t的超额流量即为最大流值。

关键点

• FIFO队列确保活跃节点按顺序处理，避免饥饿。
• 高度函数保证流只能推向更低高度的节点，最终汇点高度≥|V|时停止。
• 时间复杂度为O(V³)，实践中效率较高。

通过逐步执行Push和Relabel，算法最终将预流转化为合法最大流。