最大流问题（Relabel-to-Front 算法）
字数 2314 2025-11-21 07:12:31

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

题目描述
给定一个有向图 \(G = (V, E)\)，其中每条边 \((u, v) \in E\) 有一个非负容量 \(c(u, v) \geq 0\)。图中有一个源点 \(s\) 和一个汇点 \(t\)。最大流问题的目标是找到从 \(s\) 到 \(t\) 的最大流量，满足以下约束：

  1. 容量约束：每条边的流量不超过其容量。
  2. 流量守恒：除 \(s\) 和 \(t\) 外，每个顶点的流入流量等于流出流量。

Relabel-to-Front 算法是 Push-Relabel 算法的高效实现，通过维护每个顶点的“高度”和“超额流量”来逐步将流量推向汇点，最终得到最大流。其时间复杂度为 \(O(V^3)\)，适合处理稠密图。

解题过程

1. 基本概念

  • 预流（Preflow）：允许顶点的流入流量暂时大于流出流量（即存在“超额流量”）。
  • 高度标签（Height Label）：每个顶点 \(u\) 有一个高度 \(h[u]\)，源点高度固定为 \(|V|\)，汇点高度固定为 0。
  • 可行边：若边 \((u, v)\) 满足 \(h[u] = h[v] + 1\) 且剩余容量 \(c_f(u, v) > 0\)，则称该边为可行边。
  • 活跃顶点（Active Vertex）：超额流量 \(e[u] > 0\) 且非汇点的顶点。

2. 算法步骤

初始化

  1. 设置所有边流量为 0，剩余容量 \(c_f(u, v) = c(u, v)\)。
  2. 初始化高度：
    • \(h[s] = |V|\)（源点高度为顶点数）
    • \(h[u] = 0\)（其他顶点初始高度为 0）
  3. 从源点 \(s\) 向所有邻接点推送流量：
    • 对每条边 \((s, v)\)，推送流量 \(f(s, v) = c(s, v)\)，更新超额流量 \(e[v] = c(s, v)\)，\(e[s]\) 减少相应值。

主循环

维护一个顶点列表 \(L\)（除 \(s\) 和 \(t\) 外的所有顶点，按拓扑顺序排列）。依次处理每个顶点：

  1. 若当前顶点 \(u\) 无超额流量（\(e[u] = 0\)），则跳过。
  2. 否则，尝试通过 推送（Push） 或 重标记（Relabel） 操作处理 \(u\)：
    • 推送操作：
      • 若存在可行边 \((u, v)\)（即 \(h[u] = h[v] + 1\) 且 \(c_f(u, v) > 0\)），则推送流量 \(\Delta = \min(e[u], c_f(u, v))\)。
      • 更新流量和超额流量：
        • \(f(u, v) = f(u, v) + \Delta\)，\(f(v, u) = f(v, u) - \Delta\)
        • \(c_f(u, v) = c_f(u, v) - \Delta\)，\(c_f(v, u) = c_f(v, u) + \Delta\)
        • \(e[u] = e[u] - \Delta\)，\(e[v] = e[v] + \Delta\)
    • 重标记操作：
      • 若无可推边，则提升 \(u\) 的高度：\(h[u] = 1 + \min\{ h[v] \mid (u, v) \in E, c_f(u, v) > 0 \}\)。
  3. 若 \(u\) 仍活跃，则将其移至列表 \(L\) 的开头，重新从开头处理。

终止条件

当列表中无活跃顶点时，算法结束。此时汇点的流入流量即为最大流。

3. 示例演示

考虑一个简单图：

  • 顶点：\(s, a, b, t\)
  • 边：
    • \((s, a): c=3\)
    • \((s, b): c=2\)
    • \((a, b): c=1\)
    • \((a, t): c=4\)
    • \((b, t): c=2\)

执行过程：

  1. 初始化：
    • \(h[s] = 4\), \(h[a]=h[b]=h[t]=0\)
    • 从 \(s\) 推流：\(e[a]=3\), \(e[b]=2\)
    • 列表 \(L = [a, b]\)
  2. 处理 \(a\)：
    • 无可推边（\(h[a]=0\)，邻点高度均不低于它），重标记 \(h[a] = 1\)。
    • 推流到 \(b\)（\(\Delta=1\)）：\(e[a]=2\), \(e[b]=3\)
    • 推流到 \(t\)（\(\Delta=2\)）：\(e[a]=0\), \(e[t]=2\)
  3. 处理 \(b\)：
    • 重标记 \(h[b] = 1\)
    • 推流到 \(t\)（\(\Delta=2\)）：\(e[b]=1\), \(e[t]=4\)
    • 推流到 \(a\)（\(\Delta=1\)）：\(e[b]=0\), \(e[a]=1\)
  4. 重新处理 \(a\)：
    • 推流到 \(t\)（\(\Delta=1\)）：\(e[a]=0\), \(e[t]=5\)
  5. 无活跃顶点，结束。最大流为 5。

关键点总结

  • Relabel-to-Front 通过维护高度差保证流量向汇点移动。
  • 推送操作沿可行边推流，重标记操作提升高度以创造可行边。
  • 顶点列表的动态调整确保高效处理活跃顶点。
最大流问题（Relabel-to-Front 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。图中有一个源点 \( s \) 和一个汇点 \( t \)。最大流问题的目标是找到从 \( s \) 到 \( t \) 的最大流量，满足以下约束： 容量约束 ：每条边的流量不超过其容量。 流量守恒 ：除 \( s \) 和 \( t \) 外，每个顶点的流入流量等于流出流量。 Relabel-to-Front 算法是 Push-Relabel 算法的高效实现，通过维护每个顶点的“高度”和“超额流量”来逐步将流量推向汇点，最终得到最大流。其时间复杂度为 \( O(V^3) \)，适合处理稠密图。 解题过程 1. 基本概念 预流（Preflow） ：允许顶点的流入流量暂时大于流出流量（即存在“超额流量”）。 高度标签（Height Label） ：每个顶点 \( u \) 有一个高度 \( h[ u ] \)，源点高度固定为 \( |V| \)，汇点高度固定为 0。 可行边 ：若边 \( (u, v) \) 满足 \( h[ u] = h[ v] + 1 \) 且剩余容量 \( c_ f(u, v) > 0 \)，则称该边为可行边。 活跃顶点（Active Vertex） ：超额流量 \( e[ u ] > 0 \) 且非汇点的顶点。 2. 算法步骤 初始化 设置所有边流量为 0，剩余容量 \( c_ f(u, v) = c(u, v) \)。 初始化高度： \( h[ s ] = |V| \)（源点高度为顶点数） \( h[ u ] = 0 \)（其他顶点初始高度为 0） 从源点 \( s \) 向所有邻接点推送流量： 对每条边 \( (s, v) \)，推送流量 \( f(s, v) = c(s, v) \)，更新超额流量 \( e[ v] = c(s, v) \)，\( e[ s ] \) 减少相应值。 主循环 维护一个顶点列表 \( L \)（除 \( s \) 和 \( t \) 外的所有顶点，按拓扑顺序排列）。依次处理每个顶点： 若当前顶点 \( u \) 无超额流量（\( e[ u ] = 0 \)），则跳过。 否则，尝试通过 推送（Push） 或 重标记（Relabel） 操作处理 \( u \)： 推送操作 ： 若存在可行边 \( (u, v) \)（即 \( h[ u] = h[ v] + 1 \) 且 \( c_ f(u, v) > 0 \)），则推送流量 \( \Delta = \min(e[ u], c_ f(u, v)) \)。 更新流量和超额流量： \( f(u, v) = f(u, v) + \Delta \)，\( f(v, u) = f(v, u) - \Delta \) \( c_ f(u, v) = c_ f(u, v) - \Delta \)，\( c_ f(v, u) = c_ f(v, u) + \Delta \) \( e[ u] = e[ u] - \Delta \)，\( e[ v] = e[ v ] + \Delta \) 重标记操作 ： 若无可推边，则提升 \( u \) 的高度：\( h[ u] = 1 + \min\{ h[ v] \mid (u, v) \in E, c_ f(u, v) > 0 \} \)。 若 \( u \) 仍活跃，则将其移至列表 \( L \) 的开头，重新从开头处理。 终止条件 当列表中无活跃顶点时，算法结束。此时汇点的流入流量即为最大流。 3. 示例演示 考虑一个简单图： 顶点：\( s, a, b, t \) 边： \( (s, a): c=3 \) \( (s, b): c=2 \) \( (a, b): c=1 \) \( (a, t): c=4 \) \( (b, t): c=2 \) 执行过程 ： 初始化： \( h[ s] = 4 \), \( h[ a]=h[ b]=h[ t ]=0 \) 从 \( s \) 推流：\( e[ a]=3 \), \( e[ b ]=2 \) 列表 \( L = [ a, b ] \) 处理 \( a \)： 无可推边（\( h[ a]=0 \)，邻点高度均不低于它），重标记 \( h[ a ] = 1 \)。 推流到 \( b \)（\( \Delta=1 \)）：\( e[ a]=2 \), \( e[ b ]=3 \) 推流到 \( t \)（\( \Delta=2 \)）：\( e[ a]=0 \), \( e[ t ]=2 \) 处理 \( b \)： 重标记 \( h[ b ] = 1 \) 推流到 \( t \)（\( \Delta=2 \)）：\( e[ b]=1 \), \( e[ t ]=4 \) 推流到 \( a \)（\( \Delta=1 \)）：\( e[ b]=0 \), \( e[ a ]=1 \) 重新处理 \( a \)： 推流到 \( t \)（\( \Delta=1 \)）：\( e[ a]=0 \), \( e[ t ]=5 \) 无活跃顶点，结束。最大流为 5。 关键点总结 Relabel-to-Front 通过维护高度差保证流量向汇点移动。 推送操作沿可行边推流，重标记操作提升高度以创造可行边。 顶点列表的动态调整确保高效处理活跃顶点。