xxx 最大流问题（Dinic 算法）

题目描述
给定一个有向图，其中每条边有一个非负容量（capacity），以及两个特殊节点：源点（source）和汇点（sink）。最大流问题的目标是找到从源点到汇点的最大流量，使得每条边上的流量不超过其容量，且除源点和汇点外，每个节点的流入流量等于流出流量（流量守恒）。

解题过程循序渐进讲解

1. 基本概念回顾

• 流量（flow）：边上的实际传输量，不超过容量。
• 剩余容量（residual capacity）：边的容量减去当前流量，表示还能增加多少流量。反向边（反向边容量等于当前流量，表示可回退的流量）也计入剩余网络。
• 增广路径（augmenting path）：从源点到汇点的一条路径，其上每条边都有剩余容量 >0。
• 层次图（level graph）：通过 BFS 从源点出发，按距离分层，只保留从第 i 层指向第 i+1 层的边。

2. Dinic 算法的核心思想
Dinic 算法通过 BFS 构建层次图 + DFS 在层次图中多路增广，高效求解最大流。
优势：

• 避免 Ford-Fulkerson 中 DFS 可能多次走重复边的问题。
• 每次 BFS 后，在层次图中进行多路 DFS 增广，保证时间复杂度为 O(V²E)（对于二分图匹配为 O(√V E)）。

3. 算法步骤详解

步骤 1：初始化

• 初始化流量为 0。
• 构建剩余图：初始时与原图相同，反向边容量为 0。

步骤 2：BFS 构建层次图

• 从源点 s 开始 BFS，计算每个节点到 s 的最短距离（层级）。
• 只保留从层级 i 指向层级 i+1 的边。
• 如果汇点 t 未被 BFS 访问到，说明没有增广路，算法结束。

步骤 3：DFS 多路增广

• 在层次图中，从 s 开始 DFS，寻找一条从 s 到 t 的路径。
• DFS 时，只访问下一层级的节点。
• 找到路径后，计算路径上的最小剩余容量（瓶颈容量），增加该流量，并更新剩余图（正向边减流量，反向边加流量）。
• 关键优化：DFS 时使用“当前弧优化”，即记录每个节点当前访问到哪条边，避免重复检查已无法增广的边。

步骤 4：重复步骤 2 和 3

• 当 BFS 无法到达汇点时，算法终止，当前流量即为最大流。

4. 举例说明
考虑以下有向图（边上的数字表示容量）：

    s
   / \
  a   b
   \ / \
    c   d
     \ /
      t

边：
s→a:3, s→b:2, a→c:3, b→c:3, b→d:3, c→t:2, d→t:3

执行过程：

1. BFS 层级：s(0), a/b(1), c/d(2), t(3)。
2. DFS 增广：
   • 路径 s→a→c→t，瓶颈=2，流量+2。
   • 路径 s→b→d→t，瓶颈=2，流量+2。
   • 此时层次图中 s→b 剩余容量为 0，但 c→t 已满，需重新 BFS。
3. 第二次 BFS：新层级中可能排除 c→t（剩余容量 0），找到 s→b→c→? 无法到 t，算法结束。
   最终最大流 = 4。

5. 复杂度分析

• 时间复杂度：O(V²E)
• 空间复杂度：O(V+E)
• 当前弧优化确保每条边只被检查一次每 BFS 轮。

6. 关键点总结

• 层次图限制了 DFS 的方向，避免绕远路。
• 多路增广：一次 DFS 可能找到多条增广路径。
• 当前弧优化：避免重复检查无效边，提升效率。