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

题目描述
给定一个有向图，其中每条边有一个非负容量（capacity），表示该边能通过的最大流量。图中有一个源点（source）和一个汇点（sink）。最大流问题的目标是找到从源点到汇点的最大流量，使得每条边上的流量不超过其容量，且除源点和汇点外，每个顶点的流入流量等于流出流量（流量守恒）。

解题过程
Push-Relabel算法通过模拟水流在顶点间的“推送”和“重标记”操作来求解最大流。与增广路径类算法（如Ford-Fulkerson）不同，它维护一个预流（preflow），允许顶点的流入流量暂时大于流出流量（即存在超额流），最终通过调整使流量守恒。

1. 初始化

   • 设置源点的高度为顶点总数（|V|），其余顶点高度为0。
   • 将源点的所有出边流量设为满容量（即流量=容量），使源点的邻居获得超额流（excess flow），源点自身流量设为负的出流总和。
   • 初始化一个队列（或列表），保存所有有超额流的顶点（汇点和源点除外）。

2. 推送操作（Push）
   若顶点u有超额流，且存在一条残存边（u, v）（即容量-流量>0），且u的高度比v高1（h(u) = h(v) + 1），则沿边(u, v)推送流量：

   • 推送量 = min(u的超额流, 边的残存容量)
   • 更新边(u, v)的流量和v的超额流。若v成为新的有超额流顶点（且非源/汇），加入队列。

3. 重标记操作（Relabel）
   若顶点u有超额流，但无法推送（即所有残存边连接的邻居高度均不低于u），则重标记u的高度：

   • 新高度 = min{ h(v) | (u, v)为残存边 } + 1
   • 此操作保证后续可能发生推送。

4. 主循环
   重复从队列中取出有超额流的顶点，尝试推送或重标记，直到所有顶点的超额流为0（除源点和汇点）。此时预流变为合法流，汇点的流入流量即为最大流。

关键点

• 高度函数保证无环操作，避免死循环。
• 时间复杂度通常为O(V²E)，但在实践中常优于增广路径算法。