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

题目描述
最大流问题要求在一个有向图中，从源点（source）到汇点（sink）能传输的最大流量。每条边有一个容量（capacity），表示该边能承载的最大流量。Push-Relabel算法是一种高效求解最大流的方法，通过维护每个顶点的“预流”（preflow）和“高度标签”（height label），逐步将流量推向汇点。

解题过程

1. 初始化

   • 设置源点高度为顶点数量（|V|），其余顶点高度为0。
   • 将源点的所有出边流量设为满容量（饱和推送），并更新目标顶点的超额流量（excess flow）。
   • 源点高度保持不变，其他顶点初始高度为0。

2. 核心操作：推送（Push）与重贴标签（Relabel）

   • 推送条件：对于超额流量大于0的顶点u，若存在邻接顶点v满足以下条件，则推送流量：
     1. 边(u,v)有剩余容量（capacity - flow > 0）；
     2. u的高度比v的高度大1（h[u] = h[v] + 1）。
   • 推送操作：将min(excess[u], residual_capacity(u,v))的流量从u推送到v。
   • 重贴标签条件：若u有超额流量但无法推送（所有邻接顶点高度不低于u），则调整u的高度为min{h[v]} + 1（v为u的邻接点且边有剩余容量）。

3. 算法流程

   • 循环执行以下步骤，直到所有非源汇点的超额流量为0：
     1. 选择一个有超额流量的顶点u。
     2. 尝试向高度低1的邻接点推送流量。
     3. 若无法推送，则重贴标签增加u的高度。
   • 最终汇点的流入量即为最大流。

关键点

• 高度差保证流量向汇点方向流动，避免循环。
• 重贴标签操作防止死锁，确保进度。
• 时间复杂度为O(V²√E)，适合稠密图。

通过逐步推送和调整高度，算法最终收敛到最大流解。