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

我将为您详细讲解图论中的最大流问题及其Push-Relabel算法解法。

问题描述
最大流问题是指在一个有向图中，给定源点s和汇点t，每条边有一个非负容量，求从s到t的最大流量。Push-Relabel算法是解决此问题的高效方法，时间复杂度为O(V²E)或O(V³)。

算法核心思想
Push-Relabel算法采用"局部操作"的思想，维护一个预流（允许顶点暂时存储超额流量）和高度函数，通过两种基本操作逐步将流量推向汇点。

详细解题步骤

1. 预流初始化

   • 初始化高度函数：h[s] = V（顶点数），h[u] = 0（其他顶点）
   • 初始化流量：所有边流量为0
   • 初始化预流：从源点s出发的所有边推送其容量值的流量
   • 记录每个顶点的超额流量：excess[u] = 进入u的流量 - 离开u的流量

2. 高度函数的作用

   • 高度函数h: V → Z⁺ 满足：
     • h[s] = V
     • h[t] = 0
     • 对于残量图中的边(u,v)，有h[u] ≤ h[v] + 1
   • 高度差确保流量只能从高顶点流向低顶点

3. 基本操作：Push操作
   当顶点u有超额流量且存在边(u,v)满足：

   • h[u] = h[v] + 1
   • 残量容量cf(u,v) > 0

   推送流量：Δf = min(excess[u], cf(u,v))
   更新：

   • f(u,v) += Δf
   • excess[u] -= Δf
   • excess[v] += Δf

4. 基本操作：Relabel操作
   当顶点u有超额流量，但所有出边都不满足Push条件时：

   • 重新标记高度：h[u] = 1 + min{h[v] | (u,v)在残量图中}
   • 这为后续的Push操作创造条件

5. 算法执行流程

   初始化预流和高度
   while 存在活跃顶点（除s,t外有超额流量的顶点） do
     选择活跃顶点u
     if 存在可Push的边(u,v) then
        执行Push操作
     else
        执行Relabel操作
   end while
   

6. 算法终止条件

   • 当除源点s和汇点t外，所有顶点的超额流量都为0
   • 此时预流变为合法流，且是最大流

算法优化变种

1. FIFO Push-Relabel

   • 使用队列管理活跃顶点
   • 按先进先出顺序处理顶点
   • 时间复杂度：O(V³)

2. 最高标号优先

   • 优先处理高度最高的活跃顶点
   • 时间复杂度：O(V²√E)

3. 间隙启发式

   • 当高度出现"间隙"时，可立即确定某些顶点不可达
   • 显著提升实际性能

算法正确性保证

• 高度函数确保无环，避免无限循环
• Relabel操作保证高度单调递增
• Push操作逐步减少总超额流量
• 最终所有超额流量必能到达汇点或返回源点

实例演示
考虑简单网络：s→a→t，s→b→t，容量均为1

1. 初始化：h[s]=2，推送流量到a,b
2. a,b成为活跃顶点，推送到t
3. 超额流量归零，得到最大流=2

Push-Relabel算法因其高效性和实现简洁性，在实践中被广泛使用。