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

题目描述
给定一个有向图，其中每条边有一个非负容量（capacity），以及一个源点（source）和一个汇点（sink），求从源点到汇点的最大流量。Relabel-to-Front 算法是 Push-Relabel 算法的一种高效实现，通过维护一个顶点列表来优化操作顺序，时间复杂度为 O(V³)。

解题过程

1. 基本概念

   • 预流（Preflow）：允许顶点的流入量暂时大于流出量，每个顶点有一个超额流（excess flow）。
   • 高度函数（Height Function）：为每个顶点分配一个高度值，规定流量只能从高顶点流向低顶点。
   • 操作：Push（推送流）和 Relabel（提升高度）是核心操作。

2. 算法初始化

   • 设置源点高度为 |V|（顶点数），其余顶点高度为 0。
   • 从源点向所有相邻顶点推送满容量流，初始化预流。
   • 创建一个顶点列表 L，包含所有除源点和汇点外的顶点，顺序任意。

3. 主循环

   • 从列表 L 的头部开始遍历顶点 u：
     • 记录当前高度 old_height。
     • 循环执行以下操作，直到 u 的超额流为 0：
       • 推送操作：检查 u 的邻接边，若存在边 (u, v) 且剩余容量 > 0，且 u 的高度 = v 的高度 + 1，则沿边推送流（推送量为 min(u 的超额流, 边剩余容量)）。
       • 重标记操作：若无法推送但 u 仍有超额流，则将其高度提升为 min{ v 的高度 | (u, v) 有剩余容量 } + 1。
     • 若 u 的高度在操作中变化，将其移至列表 L 的头部（从头重新扫描）。
   • 遍历完成后，汇点的超额流即为最大流。

4. 关键点说明

   • 列表 L 的管理确保算法优先处理活跃顶点（有超额流的顶点），减少无效操作。
   • 高度提升保证流最终能向汇点方向移动，避免死循环。

示例
假设图有顶点 {s, a, b, t}，边容量：s→a:3, s→b:2, a→b:1, a→t:2, b→t:3。

• 初始化：s 高度=4，推送 s→a:3, s→b:2，列表 L=[a, b]。
• 处理 a：推送 a→t:2, a→b:1（超额流清零）。
• 处理 b：推送 b→t:3（超额流清零），算法终止，最大流=5。

通过维护顶点列表和高度优化，Relabel-to-Front 算法高效解决了最大流问题。