xxx 最大流问题（Dinic算法） 题目描述 给定一个有向图，其中每条边有一个非负容量（capacity）。图中有一个源点（source）和一个汇点（sink）。最大流问题的目标是找到从源点到汇点的最大流量，使得每条边上的流量不超过其容量，且除源点和汇点外，所有顶点的流入流量等于流出流量（流量守恒）。 解题过程 Dinic算法是一种高效的最大流算法，结合了BFS分层和DFS多路增广。其核心思想是通过构建分层图（Level Graph）来指导增广路径的选择，减少重复计算。 步骤1：初始化 初始化残余网络（Residual Graph），初始时每条边的流量为0，残余容量等于原始容量。 最大流初始值设为0。 步骤2：BFS构建分层图 从源点s出发进行BFS，为每个顶点分配一个层级（level），表示从s到该顶点的最短路径（边数）。 具体过程： 初始化队列，将s的层级设为0，入队。 遍历队列，对每个顶点u，检查其所有出边（u→v），若v未被访问且边的残余容量大于0，则设置v的层级为u的层级+1，并将v入队。 若汇点t未被分配到层级（不可达），说明已无增广路径，算法终止。 步骤3：DFS多路增广 在分层图上，从s出发进行DFS，寻找一条从s到t的路径，并计算路径上的最小残余容量（瓶颈容量）。 增广过程： 从当前顶点u开始，尝试所有满足层级差为1（v的层级 = u的层级 + 1）且残余容量大于0的边（u→v）。 递归向下搜索，直到到达t或无法前进。 若到达t，则沿路径回溯，更新每条边的残余容量（正向边减少流量，反向边增加流量），并返回瓶颈容量。 若某条边已无法增广，则在本次DFS中不再访问（通过标记避免重复）。 重复执行DFS，直到无法找到新的增广路径。 步骤4：循环执行 重复步骤2和步骤3（每次BFS后执行多次DFS），直到BFS无法到达t。 最终的最大流值为所有增广路径的流量之和。 关键优化 多路增广 ：一次BFS后执行多次DFS，充分利用分层结构。 当前弧优化 ：在DFS中记录每个顶点当前检查到的边，避免重复检查无效边。 复杂度分析 时间复杂度：O(V²E)，其中V为顶点数，E为边数。在单位容量图中可优化至O(E√V)。 空间复杂度：O(V+E)用于存储图结构。 通过分层图限制增广方向，Dinic算法显著减少了无效搜索，比基础的Ford-Fulkerson方法更高效。