xxx 最大流问题（FIFO Push-Relabel 算法）
字数 2138 2025-11-05 23:45:42

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

题目描述
给定一个有向图 \(G = (V, E)\)，每条边 \((u, v) \in E\) 有一个非负容量 \(c(u, v) \geq 0\)。图中有一个源点 \(s\) 和一个汇点 \(t\)。最大流问题的目标是找到从 \(s\) 到 \(t\) 的最大流量，使得每条边上的流量不超过其容量，且除 \(s\) 和 \(t\) 外，每个顶点的流入流量等于流出流量（流量守恒）。FIFO Push-Relabel 算法是一种高效求解最大流问题的方法，它通过维护每个顶点的“高度”和“超额流量”，以先进先出（FIFO）的顺序处理活跃顶点，实现近似 \(O(|V|^3)\) 的时间复杂度。

解题过程

  1. 核心概念

    • 预流（Preflow）：允许顶点的流入流量暂时大于流出流量（即顶点可存储超额流量），但边流量仍需满足容量约束。
    • 高度函数（Height Function）：为每个顶点 \(u\) 分配一个整数高度 \(h(u)\)，初始时 \(h(s) = |V|\)，\(h(u) = 0\)（\(u \neq s\)）。算法保证：如果存在边 \((u, v)\) 的剩余容量为正，则 \(h(u) \leq h(v) + 1\)。
    • 超额流量（Excess Flow）：顶点 \(u\) 的流入与流出流量之差，记作 \(e(u)\)。源点 \(s\) 和汇点 \(t\) 的超额流量始终为 0，其他顶点可能为正。
    • 活跃顶点（Active Vertex）：满足 \(e(u) > 0\) 且 \(u \notin \{s, t\}\) 的顶点。

  2. 算法步骤
    初始化：

    • 设置高度：\(h(s) = |V|\)，\(h(u) = 0\)（\(\forall u \neq s\)）。
    • 初始化流量：将所有边流量设为 0，然后从 \(s\) 向所有邻接点推送尽可能多的流量（即 \(f(s, v) = c(s, v)\)），使 \(s\) 的邻接点获得超额流量。
    • 将初始有超额流量的顶点加入 FIFO 队列。

    主循环（直到队列为空）：
    从队列头部取出一个顶点 \(u\)，尝试通过以下操作消除其超额流量：

    • 推送操作（Push）：若存在边 \((u, v)\) 的剩余容量 \(r(u, v) > 0\) 且 \(h(u) = h(v) + 1\)，则沿该边推送流量 \(\Delta = \min(e(u), r(u, v))\)。推送后更新 \(e(u)\) 和 \(e(v)\)，若 \(v\) 是新变为活跃的顶点（且 \(v \notin \{s, t\}\)），则将其加入队列尾部。
    • 重标记操作（Relabel）：若 \(u\) 仍有超额流量（\(e(u) > 0\)）但无法推送（所有剩余边满足 \(h(u) \leq h(v)\)），则将 \(h(u)\) 提高到 \(\min\{ h(v) +1 \mid (u,v) \in E, r(u,v)>0 \}\)。之后将 \(u\) 重新加入队列尾部（因为高度提升后可能产生新的推送机会）。

  3. 终止与正确性

    • 当队列为空时，所有顶点的超额流量均为 0，预流变为合法流，且此时流量最大（根据高度约束，无法从 \(s\) 到 \(t\) 找到增广路径）。
    • 算法正确性依赖于高度函数的性质：源点高度始终为 \(|V|\)，汇点高度始终为 0，且高度差限制保证推送操作的合理性。

  4. 复杂度分析

    • 重标记操作次数为 \(O(|V|^2)\)，饱和推送（使边满流）次数为 \(O(|V||E|)\)，非饱和推送次数为 \(O(|V|^2|E|)\)。
    • 使用 FIFO 队列管理活跃顶点，总时间复杂度为 \(O(|V|^3)\)。

示例说明
考虑一个简单图：顶点集 \(\{s, a, b, t\}\)，边容量为 \(c(s,a)=3, c(s,b)=2, c(a,b)=1, c(a,t)=2, c(b,t)=3\)。

  1. 初始化：从 \(s\) 推 3 到 \(a\)（\(e(a)=3\)），推 2 到 \(b\)（\(e(b)=2\)），队列为 \([a, b]\)。
  2. 处理 \(a\)：推 2 到 \(t\)（剩余 \(e(a)=1\)），推 1 到 \(b\)（\(e(b)=3\)），队列变为 \([b, a]\)。
  3. 处理 \(b\)：推 3 到 \(t\)（\(e(b)=0\)），队列剩 \([a]\)。
  4. 处理 \(a\)：重标记 \(h(a)=1\) 后无法推送，队列空。最终最大流为 5（\(s \to a \to t\) 流 2，\(s \to a \to b \to t\) 流 1，\(s \to b \to t\) 流 2）。
xxx 最大流问题（FIFO Push-Relabel 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。图中有一个源点 \( s \) 和一个汇点 \( t \)。最大流问题的目标是找到从 \( s \) 到 \( t \) 的最大流量，使得每条边上的流量不超过其容量，且除 \( s \) 和 \( t \) 外，每个顶点的流入流量等于流出流量（流量守恒）。FIFO Push-Relabel 算法是一种高效求解最大流问题的方法，它通过维护每个顶点的“高度”和“超额流量”，以先进先出（FIFO）的顺序处理活跃顶点，实现近似 \( O(|V|^3) \) 的时间复杂度。 解题过程 核心概念 预流（Preflow） ：允许顶点的流入流量暂时大于流出流量（即顶点可存储超额流量），但边流量仍需满足容量约束。 高度函数（Height Function） ：为每个顶点 \( u \) 分配一个整数高度 \( h(u) \)，初始时 \( h(s) = |V| \)，\( h(u) = 0 \)（\( u \neq s \)）。算法保证：如果存在边 \( (u, v) \) 的剩余容量为正，则 \( h(u) \leq h(v) + 1 \)。 超额流量（Excess Flow） ：顶点 \( u \) 的流入与流出流量之差，记作 \( e(u) \)。源点 \( s \) 和汇点 \( t \) 的超额流量始终为 0，其他顶点可能为正。 活跃顶点（Active Vertex） ：满足 \( e(u) > 0 \) 且 \( u \notin \{s, t\} \) 的顶点。 算法步骤 初始化 ： 设置高度：\( h(s) = |V| \)，\( h(u) = 0 \)（\( \forall u \neq s \)）。 初始化流量：将所有边流量设为 0，然后从 \( s \) 向所有邻接点推送尽可能多的流量（即 \( f(s, v) = c(s, v) \)），使 \( s \) 的邻接点获得超额流量。 将初始有超额流量的顶点加入 FIFO 队列。 主循环（直到队列为空） ： 从队列头部取出一个顶点 \( u \)，尝试通过以下操作消除其超额流量： 推送操作（Push） ：若存在边 \( (u, v) \) 的剩余容量 \( r(u, v) > 0 \) 且 \( h(u) = h(v) + 1 \)，则沿该边推送流量 \( \Delta = \min(e(u), r(u, v)) \)。推送后更新 \( e(u) \) 和 \( e(v) \)，若 \( v \) 是新变为活跃的顶点（且 \( v \notin \{s, t\} \)），则将其加入队列尾部。 重标记操作（Relabel） ：若 \( u \) 仍有超额流量（\( e(u) > 0 \)）但无法推送（所有剩余边满足 \( h(u) \leq h(v) \)），则将 \( h(u) \) 提高到 \( \min\{ h(v) +1 \mid (u,v) \in E, r(u,v)>0 \} \)。之后将 \( u \) 重新加入队列尾部（因为高度提升后可能产生新的推送机会）。 终止与正确性 当队列为空时，所有顶点的超额流量均为 0，预流变为合法流，且此时流量最大（根据高度约束，无法从 \( s \) 到 \( t \) 找到增广路径）。 算法正确性依赖于高度函数的性质：源点高度始终为 \( |V| \)，汇点高度始终为 0，且高度差限制保证推送操作的合理性。 复杂度分析 重标记操作次数为 \( O(|V|^2) \)，饱和推送（使边满流）次数为 \( O(|V||E|) \)，非饱和推送次数为 \( O(|V|^2|E|) \)。 使用 FIFO 队列管理活跃顶点，总时间复杂度为 \( O(|V|^3) \)。 示例说明 考虑一个简单图：顶点集 \( \{s, a, b, t\} \)，边容量为 \( c(s,a)=3, c(s,b)=2, c(a,b)=1, c(a,t)=2, c(b,t)=3 \)。 初始化：从 \( s \) 推 3 到 \( a \)（\( e(a)=3 \)），推 2 到 \( b \)（\( e(b)=2 \)），队列为 \( [ a, b ] \)。 处理 \( a \)：推 2 到 \( t \)（剩余 \( e(a)=1 \)），推 1 到 \( b \)（\( e(b)=3 \)），队列变为 \( [ b, a ] \)。 处理 \( b \)：推 3 到 \( t \)（\( e(b)=0 \)），队列剩 \( [ a ] \)。 处理 \( a \)：重标记 \( h(a)=1 \) 后无法推送，队列空。最终最大流为 5（\( s \to a \to t \) 流 2，\( s \to a \to b \to t \) 流 1，\( s \to b \to t \) 流 2）。