Dinic 算法

介绍用于最大流问题的 Dinic C++ 实现

简介

Dinic 算法（或称 Dinitz 算法）是解决最大流问题的常用算法之一，其设计思想与 Edmonds-Karp 算法非常接近。

Dinic 算法首先尝试构造一个网络流的分层图，随后在分层图中不断搜索从源点到汇点的阻塞流，直到无法再找到为止。每次搜索成功阻塞流，就立即调整原先的网络流量分配，并更新最大流的值。

Dinic 算法的时间复杂度为 $O(V^2E)$，其中 $|V|$ 表示顶点数，$|E|$ 表示边数。

定义 $F$ 为残存流矩阵，初始化 $F$ 为流网络的容量限制；定义 $maxf$ 为最大流值，初始化为 $0$。
接下来不断地尝试使用 BFS 构造分层图，直到分层图不再包含汇点时停止。
注释
使用 $level$ 数组存储分层图，$level$ 数组也可以同时充当 $used$ 数组，以免重复访问节点。
对每次构造得到的分层图，重复通过 DFS 访问图中阻塞流上的每条路径。每条路径访问完毕后更新原先的残存流 $F$ 和最大流值 $maxf$。
注释
这里阻塞流上的路径等同于 Edmonds-Karp 算法中的增广路径。由于这些路径是通过同一次 BFS 找到的，因此这些路径共享相同的分层图，一条路径对流的增广不会影响其他路径。在 DFS 过程中，同步递归地计算一条阻塞流路径的流值，并在返回时更新残存流 $F$。