xxx 最大流问题（FIFO Push-Relabel算法） 题目描述 给定一个有向图，其中每条边有一个非负容量（capacity），以及一个源点（source）和一个汇点（sink），求从源点到汇点的最大流（maximum flow）。FIFO Push-Relabel 算法是 Push-Relabel 算法家族的一种高效实现，它使用先进先出（FIFO）队列管理活跃节点（active nodes），通过局部操作（推送流和重贴标签）逐步逼近最大流。 解题过程 1. 基本概念 流（flow） ：边的实际流量，不能超过容量，且满足流量守恒（除源点和汇点外，流入等于流出）。 预流（preflow） ：允许节点暂时持有“盈余流量”（excess flow），即流入大于流出。 高度函数（height function） ：为每个节点分配一个高度值，规定流只能从高节点流向低节点（类似水流向下）。 活跃节点（active node） ：除源点和汇点外，盈余流量大于 0 的节点。 2. 算法初始化 设置所有边流量为 0。 设置源点高度为节点总数 \( n \)，其他节点高度为 0。 从源点向所有邻居推送流量（推满容量），使源点邻居获得盈余流量，标记这些邻居为活跃节点，加入 FIFO 队列。 3. 核心操作 算法循环处理队列中的活跃节点，直到队列为空： 推送操作（Push） ： 对于当前节点 \( u \) 的某条边 \( (u, v) \)，若满足： \( u \) 有盈余流量（excess[ u ] > 0）； 边有剩余容量（capacity(u,v) - flow(u,v) > 0）； \( u \) 的高度比 \( v \) 高 1（height[ u] == height[ v ] + 1）。 则推送流量 \( \Delta = \min(\text{excess}[ u ], \text{剩余容量}) \) 到 \( v \)。更新流量和盈余值。若 \( v \) 是新活跃节点（且不是源/汇），加入队列。 重贴标签操作（Relabel） ： 若 \( u \) 有盈余，但无法推送（所有邻居高度不低于 \( u \)），则抬高 \( u \) 的高度： \[ \text{height}[ u] = 1 + \min \{ \text{height}[ v ] \mid (u,v) \text{ 有剩余容量} \} \] 重贴标签后，\( u \) 可能具备推送条件，继续处理。 4. 终止条件 当队列中无活跃节点时，汇点无法再接收更多流量，算法结束。此时汇点的流入量即为最大流。 5. 示例说明 考虑一个简单图： 节点：s（源），a，b，t（汇） 边容量：s→a:3, s→b:2, a→b:1, a→t:2, b→t:3 初始化： 高度：h[ s]=4, h[ a]=h[ b]=h[ t ]=0 从 s 推流到 a 和 b：流分别为 3 和 2，盈余 excess[ a]=3, excess[ b]=2，队列=[ a, b ] 处理队列： 处理 a：尝试推送到 b（高度差 1），推流 1（边 a→b 容量 1）；再推送到 t（高度差 2），推流 2。a 盈余归 0，队列=[ b ] 处理 b：推送到 t（高度差 3），推流 3，b 盈余归 0，队列空。 最终最大流为 5（s→a:3 + s→b:2 或 t 流入 5）。 关键点 FIFO 队列确保活跃节点按顺序处理，避免饥饿。 高度函数保证流方向合理，重贴标签避免死锁。 时间复杂度为 \( O(V^3) \)，实践中常优于理论界。