更新 $ e(u) -= \Delta $，$ e(v) += \Delta $。  

 其中 $ E_f $ 是剩余网络中的边。  

xxx 最大流问题（Relabel-to-Front 算法） 问题描述 最大流问题是在一个有向图中，从源点 \( s \) 到汇点 \( t \) 的流量分配问题。每条边有一个容量限制，目标是最大化从 \( s \) 到 \( t \) 的总流量。Relabel-to-Front 是 Push-Relabel 算法的一种高效实现，通过维护高度函数和超额流量，以 \( O(V^3) \) 时间复杂度解决该问题。 解题步骤详解 基本概念 剩余容量 ：边 \( (u, v) \) 的剩余容量为 \( c_ f(u, v) = c(u, v) - f(u, v) \)，其中 \( c \) 是容量，\( f \) 是当前流量。 高度函数 \( h(u) \)：每个顶点的高度，满足 \( h(s) = |V| \)，\( h(t) = 0 \)，且对于剩余网络中的边 \( (u, v) \)，有 \( h(u) \leq h(v) + 1 \)。 超额流量 \( e(u) \)：流入 \( u \) 的流量减去流出 \( u \) 的流量（\( u \neq s, t \)）。 初始化 设置所有边流量 \( f(u, v) = 0 \)。 初始化高度：\( h(s) = |V| \)，其他顶点 \( h(u) = 0 \)。 从源点 \( s \) 向所有邻接顶点推送流量：对每个 \( (s, v) \)，设置 \( f(s, v) = c(s, v) \)，并更新 \( e(v) = c(s, v) \)，\( e(s) \) 减少相应值。 算法主循环 维护一个顶点列表 \( L \)（除 \( s, t \) 外的所有顶点），按顺序处理每个顶点： 推送操作 （Push）： 若顶点 \( u \) 有超额流量 \( e(u) > 0 \)，检查剩余网络中的边 \( (u, v) \)。 如果 \( h(u) = h(v) + 1 \) 且 \( c_ f(u, v) > 0 \)，则推送流量： \[ \Delta = \min(e(u), c_ f(u, v)), \quad f(u, v) += \Delta, \quad f(v, u) -= \Delta \] 更新 \( e(u) -= \Delta \)，\( e(v) += \Delta \)。 重标高度 （Relabel）： 若 \( u \) 有超额流量但无法推送（所有邻接边不满足高度条件），则设置： \[ h(u) = 1 + \min\{ h(v) \mid (u, v) \in E_ f \} \] 其中 \( E_ f \) 是剩余网络中的边。 重复推送或重标直到 \( u \) 的超额流量为 0，然后处理 \( L \) 中下一个顶点。 处理完 \( L \) 后回到列表开头，直到所有顶点超额流量为 0。 终止条件 当所有顶点（除 \( s, t \)）的超额流量为零时终止。此时从 \( s \) 发出的总流量即为最大流。 关键点说明 高度函数 防止流量形成循环，确保流向汇点 \( t \)。 顶点列表顺序 通过轮流处理避免饥饿现象。 复杂度 ：最坏 \( O(V^3) \)，但实际效率常优于其他最大流算法。 通过以上步骤，Relabel-to-Front 算法逐步调整流量与高度，最终找到最大流。