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

题目描述
最大流问题是指在一个有向图中，每条边有一个容量限制，求从源点 s 到汇点 t 的最大流量。Push-Relabel 算法是一种高效求解最大流问题的方法，它通过维护每个节点的“高度”和“超额流”来逐步将流量推向汇点。

解题过程

1. 初始化

   • 设置源点 s 的高度为节点总数 n，其余节点高度为 0。
   • 将源点 s 的所有出边饱和推流（即推送流量等于边容量），使相邻节点获得超额流（流入量减去流出量）。
   • 示例：若图有 4 个节点（s, a, b, t），s 的高度初始化为 4，a 和 b 的高度为 0。s 到 a 的边容量为 3，则推送流量 3 到 a，a 的超额流变为 3。

2. 选择活动节点

   • 活动节点定义为除源点 s 和汇点 t 外、超额流大于 0 的节点。
   • 算法反复从活动节点中选择一个进行操作（如用队列维护）。

3. 推流操作（Push）

   • 对于活动节点 u，检查其出边（u, v）：
     • 若边剩余容量 > 0 且 u 的高度 = v 的高度 + 1，则推送流量 min(超额流, 剩余容量) 到 v。
   • 示例：若节点 u 的超额流为 2，边 (u, v) 剩余容量为 1，则推送流量 1 到 v，u 的超额流减为 1，v 的超额流增加 1。

4. 重贴标签（Relabel）

   • 若当前节点 u 有超额流，但无法推流（所有出边要么已满，要么相邻节点高度不低于 u），则将 u 的高度提升到比最低的可行邻居节点高度多 1。
   • 示例：u 的高度为 2，其邻居 v 和 w 的高度分别为 2 和 3，则 u 的新高度为 min(2,3) + 1 = 3。

5. 终止条件

   • 当除 s 和 t 外无活动节点时，算法结束。此时汇点 t 接收的流量即为最大流。

关键点

• 高度差保证流量不会反向流回源点。
• 复杂度为 O(V²√E)，适合处理大规模网络流问题。