xxx 最大流问题（Push-Relabel算法） 问题描述 Push-Relabel算法是一种求解有向图最大流问题的高效方法。给定一个有向图，其中每条边有一个非负容量，以及源点s和汇点t，目标是找到从s到t的最大流量。与增广路径类算法（如Ford-Fulkerson）不同，Push-Relabel算法通过局部操作（推送流量和重贴标签）逐步优化预流（允许节点暂时超额持有流量），最终得到最大流。 解题步骤 初始化 设置所有边的流量为0。 对源点s，将所有出边的流量设为满容量（即预流从s推送到相邻节点），使s的相邻节点持有超额流量（excess flow）。 初始化每个节点的高度（height）：源点s的高度为节点总数n，其他节点高度为0。 核心操作 推送（Push）操作 ： 若某超额节点u（除s和t）存在一条残量边(u,v)（即容量-流量>0），且u的高度大于v的高度（h[ u] = h[ v] + 1），则沿(u,v)推送流量。推送量为min(excess[ u], residual_ capacity(u,v))。推送后更新u和v的超额流量。 重贴标签（Relabel）操作 ： 若u是超额节点，但无法推送流量（所有残量邻接点的高度都不低于u），则将u的高度提升到比其最低残量邻接点高1（即h[ u] = min{h[ v ]} + 1，v为残量邻接点）。 循环执行 重复选择超额节点（除s和t）进行Push或Relabel操作，直到没有超额节点存在。此时，汇点t接收的流量即为最大流。 优化技巧 使用队列管理超额节点，避免重复检查。 引入“间隙启发式”（Gap Heuristic）：若某高度k的节点消失（无节点处于高度k），则所有高度大于k的节点可标记为不可达，直接重设高度以加速收敛。 示例说明 假设图有节点s、a、t，边(s,a)容量3，(a,t)容量2。初始化后，s的高度为2，a的高度为0。 从s向a推送流量2（受限于(a,t)容量），a超额2，t无超额。 a无法向t推送（因h[ a]=0 < h[ t]=0），故重贴标签a：h[ a] = h[ t ]+1=1。 a向t推送流量2，a超额归零，t接收流量2。算法终止，最大流为2。 通过局部操作避免全局路径搜索，Push-Relabel算法在稀疏图和稠密图中均表现优异，时间复杂度可达O(V²√E)。