介绍用于最大流问题的 Edmonds-Karp C++ 实现
简介
Edmonds-Karp 算法是一种用于解决最大流问题的算法，它是 Ford-Fulkerson 方法的一种特定实现。最大流问题是指在一个有向图中，找到使得源点净流出量最大的一种网络流量分配。在 Edmonds-Karp 算法中，我们首先从网络容量限制中导出初始的残存网络，然后不断使用 BFS 搜索增广路径，直到无法找到增广路径为止。在每次增广路径找到后，我们沿着增广路径增广网络流。由于残存流（增广路径的流）对流的递增的值，等同于流的值加上残存流的值，因此我们可以通过不断重复增广路径的过程，直到无法找到增广路径为止，得到最大流。
Edmonds-Karp 算法的时间复杂度为 $O(VE^2)$，其中 $|V|$ 表示顶点数，$|E|$ 表示边数。
实现方法
定义 $F$ 为残存流矩阵，初始化 $F$ 为流网络的容量限制；定义 $maxf$ 为最大流值，初始化为 $0$。
随后不断使用 BFS 在该残存流中搜索增广路径，直到不存在增广路径为止。
根据单源最短路径的特性，一条最短路径一定不含回路，所以搜索过程中不会重复访问节点。使用 $last$ 数组记录搜索 BFS 搜索树，以记录增广路径；同时，$last$ 数组还可以充当 $used$ 数组的作用，防止访问回路。使用 $aug$ 数组同步递推计算该增广路径的流值。
- 根据 $last$ 数组，回溯遍历该增广路径，更新残存流 $F$。
具体而言，对于增广路径中的边 $(u,v)$，让残存流 $F$ 的 $(u,v)$ 边减去增广路径的流值，而 $(v,u)$ 边加上增广路径的流值。这是因为增广路径对流的递增，等同于对残存流的缩减。
- 最后将最大流值 $maxf$ 加上该增广路径的流值。
实现细节
算法原型中的流网络不允许存在反平行边，但在代码实现中则可以存在反平行边。在代码层使用反平行边等效于分别将两条边在图中各计算一次。
对于重复边，我们需要将其合并为一条边。
算法原型中使用了网络流和残存流两个概念模型；而在代码实现中，我们仅编码了残存流——即把网络流和残存流在代码层面上进行了合并。
代码实现
P2740 【[USACO4.2]草地排水Drainage Ditches】 C++ 代码
-
Thomas H.Cormen.,《算法导论》（第三版）
-
俞勇,《ACM国际大学生程序设计竞赛——知识与入门》
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
