最大流问题（Dinic算法）

题目描述
最大流问题是指在一个有向图中，每条边有一个容量限制，求从源点（s）到汇点（t）的最大流量。Dinic算法是一种高效的最大流算法，通过分层图（BFS）和阻塞流（DFS多路增广）的结合，时间复杂度为O(V²E)，适合处理稀疏图或中等规模的稠密图。

解题步骤

1. 初始化

   • 构建残量图：初始时残量容量等于原始容量，反向边容量为0。
   • 定义数组level[]记录BFS分层中每个节点的深度（从源点s出发的距离）。

2. 分层图（BFS）

   • 从源点s开始BFS，给每个节点标记层级（level[v] = level[u] + 1）。
   • 若汇点t不可达（level[t]未定义），说明已无增广路，算法终止。
   • 注意：BFS时只遍历残量容量大于0的边。

3. 阻塞流（DFS多路增广）

   • 从源点s开始DFS，只允许向深度增加1的邻点（level[v] == level[u] + 1）推送流量。
   • 对当前节点u，尝试所有允许的边，计算最小残量容量minFlow，并递归向v推送流量。
   • 若某边流量已用尽，在DFS中标记为“已阻塞”，避免重复检查。
   • 回溯时更新残量容量：正向边减少流量，反向边增加等量流量。

4. 迭代优化

   • 重复步骤2和3，直到BFS无法到达汇点t。
   • 每次迭代后，分层图会因流量更新而变化，确保算法逐步逼近最大流。

实例演示
以简单图为例：s→A（容量3），s→B（容量2），A→t（容量2），B→t（容量3），A→B（容量1）。

• 第一轮BFS：层级s(0)、A(1)、B(1)、t(2)。
• DFS多路增广：s→A→t推送流量2，s→B→t推送流量2，残量图中s→A剩1，A→B剩1。
• 第二轮BFS：层级s(0)、A(1)、B(1)、t(2)。
• DFS增广：s→A→B→t推送流量1，总流量达到5（最大流）。

关键点

• Dinic算法通过分层避免DFS的盲目性，多路增广减少递归次数。
• 反向边保证流量可重新分配，确保最优解。
• 实际代码需用邻接表存储图，并优化DFS的边遍历顺序（如当前弧优化）。