xxx 最大流问题（Dinic算法）

题目描述
给定一个有向图，其中每条边有一个非负容量（capacity），表示该边能通过的最大流量。图中有一个特定的源点（source）和一个特定的汇点（sink）。最大流问题的目标是找出从源点到汇点的最大流量，即网络中能通过源点发送到汇点的最大数据量或物质流，同时满足每条边的流量不超过其容量，并且除源点和汇点外，每个节点的流入流量等于流出流量（流量守恒）。

解题过程

1. 基本概念与残量图

   • 流量网络：图 G=(V, E) 中，每条边 (u, v) 有容量 c(u, v) ≥ 0。源点 s 和汇点 t 是 V 中的两个不同节点。
   • 可行流：满足容量限制（每条边流量 ≤ 容量）和流量守恒（除 s 和 t 外，流入=流出）的流函数 f。
   • 残量图：对于当前流 f，构建残量图 G_f，其中边的残量容量定义为：
     • 若原边 (u, v) 有容量 c(u, v)，当前流量为 f(u, v)，则残量图中边 (u, v) 的残量容量为 c(u, v) - f(u, v)（表示还能增加多少流量）。
     • 同时，为每条边 (u, v) 添加反向边 (v, u)，其残量容量为 f(u, v)（表示能减少多少流量，即回退流量的能力）。
   • 增广路径：在残量图中从 s 到 t 的一条路径，路径上所有边的残量容量均 > 0。沿该路径可增加流量（增加量为路径上最小残量容量）。

2. Dinic算法核心思想

   • 算法通过多轮 BFS 和 DFS 结合来高效寻找增广路径：
     1. BFS 构建分层图：从源点 s 出发进行 BFS，为每个节点分配一个层数（距离 s 的最短路径边数）。在残量图中，只保留从层数 i 到层数 i+1 的边，形成分层图。这确保每次增广沿最短路径进行。
     2. DFS 进行多路增广：在分层图中，从 s 开始进行 DFS，寻找一条从 s 到 t 的路径，并计算路径上的最小残量容量（瓶颈值）。沿该路径增加流量，并更新残量图（减少正向边容量，增加反向边容量）。DFS 会尝试当前节点的所有可能分支，直到无法到达 t 为止，实现一次 DFS 完成多路增广。
     3. 重复直到无法增广：当分层图中无法从 s 到达 t 时，算法终止。否则，重新进行 BFS 构建新的分层图，重复步骤。

3. 算法步骤详解

   • 初始化：设置初始流 f 为 0，残量图初始化为原图（反向边容量为 0）。
   • 主循环：
     • 步骤1：BFS 构建分层图
       从 s 开始 BFS，计算每个节点到 s 的距离（层数）。如果 t 不可达，则算法结束，返回最大流 f。
     • 步骤2：DFS 多路增广
       在分层图中，从 s 开始 DFS。对于当前节点 u，遍历其所有出边 (u, v)，若 v 的层数恰好是 u 的层数+1，且边 (u, v) 的残量容量 > 0，则递归访问 v。
       • 若到达 t，则沿路径回溯，更新流量：路径上所有边的残量容量减少流量增量 Δ（瓶颈值），反向边增加 Δ。累计 Δ 到总流量。
       • 若当前节点 u 无法到达 t（所有出边被阻塞），则标记 u 为“已阻塞”，后续 DFS 跳过该节点。
     • 重复步骤1和2，直到 BFS 无法到达 t。

4. 示例说明
   考虑一个简单网络：
   节点：s, A, B, t
   边：(s→A, cap=3), (s→B, cap=2), (A→B, cap=1), (A→t, cap=2), (B→t, cap=3)

   • 第一轮 BFS：层数 s(0), A(1), B(1), t(2)。分层图包含边 s→A, s→B, A→t, B→t（A→B 不符合层数差1，被忽略）。
   • DFS 增广：从 s 开始，可能路径 s→A→t，瓶颈值 min(3,2)=2，更新流量后残量变化；然后路径 s→B→t，瓶颈值 min(2,3)=2，更新流量。此时总流为4。
   • 第二轮 BFS：层数 s(0), A(1), B(1), t(2) 仍有效，但残量边 s→A(剩1), s→B(剩0), A→t(剩0), B→t(剩1)。BFS 路径 s→A→B→t（A→B 残量1，B→t 残量1），瓶颈值1，更新流量。总流变为5。
   • 第三轮 BFS：t 不可达，算法结束。最大流为5。

5. 复杂度与优点

   • 时间复杂度：O(V²E)，其中 V 是节点数，E 是边数。对于单位容量图，复杂度可优化至 O(E√V)。
   • 优点：通过分层图和多路增广，减少增广次数，比 Ford-Fulkerson 更高效，尤其适合稠密图。