AI summary
type
status
date
slug
summary
category
tags
icon
password
友情提示：请学完图论基本知识再来阅读此篇文章。 这里只有 dfs 求解（Ford），EK 和 Dinic，没有什么神仙 HLPP，因为作者太菜了自己也不会。

最大流问题

最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。
下面我们用一个例子来直观理解网络最大流问题：
notion image
如上图所示，S处是一个水源，图中的弧是水管，管道由于材质、直径的不同，其所能承受的输水量也不同，所以就出现了下图所示的不同数值的弧，我们的目标是将水源从 S 通过管道运输到 T 点，且在满足管道能承受的输水量的前提下尽可能使得输送到 T 点的水最大化。

Ford-Fulkerson 算法

残存网络 & 增广路径

残存网络 其实就是用边的剩余容量来表示每条边，如图所示的残存网络。S->v2 这条边上的数字“2”代表这条边剩余可通过容量为 2。
在残存网络上，一条能从起点 S 到达起点 T 的流量大于 0 的路径就被称为 增广路径，通过增广路径，流量一定会增加。
该算法概况起来，就是在残存网络中不断寻找增广路径，每找到一条增广路径，就递增最大流 f，并更新残存网络，直到残存网络中不存在增广路径，则此时 f 即为最终的最大流。
Ford-Fulkerson 算法是通过 DFS（深度优先遍历）的方式在当前残存网络中寻找增广路径的。
根据木桶原理，增广路径的流量等于该路径的边的最小剩余流量。如下图所示的增广路径，它的流量就是 3，因为 v4->t 的容量为 3
在找到增广路径后，我们要更新残存网络。首先就是对该增广路径的正向边进行更新，将正向边的剩余流量全部减去 3，然后对该增广路径的反向边进行更新（反向边在初始化的时候，剩余流量都为0，所以在上面的图中没有画出来，反向边的作用就是让算法可以反悔，从而通过多次迭代，找到最优解），反向边的剩余流量全部加上 3：
notion image
添加反向边是这一算法能够精确求解最大流问题的基础保障。
初次接触这一方法的读者可能察觉到一个违反直觉的情形——反向边的流量   可能是一个负值。实际上我们可以将反向边流量的减少视为反向边剩余容量的增加——这也与退流的意义相吻合——反向边剩余容量的增加意味着我们接下来可能通过走反向边来和原先正向的增广抵消，代表一种「反悔」的操作。
以下案例有可能帮助你理解这一过程。假设 G 是一个单位容量的网络，我们考虑以下过程：
  • G 上有多条增广路，其中，我们选择进行一次先后经过 u,v 的增广（如左图所示），流量增加 。
  • 我们注意到，如果进行中图上的增广，这个局部的最大流量不是 1 而是 2。但由于指向 u 的边和从 v 出发的边在第一次增广中耗尽了容量，此时我们无法进行中图上的增广。这意味着我们当前的流是不够优的，但局部可能已经没有其他（只经过原图中的边而不经过反向边的）增广路了。
  • 现在引入退流操作。第一次增广后，退流意味着  增加了 1 剩余容量，即相当于新增 (v,u) 这条边，因此我们可以再进行一次先后经过 p,v,u,q 的增广（如右图橙色路径所示）。无向边 (u,v) 上的流量在两次增广中抵消，我们惊奇地发现两次增广叠加得到的结果实际上和中图是等价的。
  • 然后重复上述过程，直到找不到增广路径，算法结束。
notion image
我们大致了解了 Ford–Fulkerson 增广的思想，可是如何证明这一方法的正确性呢？为什么增广结束后的流是一个最大流？实际上，Ford–Fulkerson 增广的正确性和最大流最小割定理（The Maxflow-Mincut Theorem）等价。这里略了。
在整数流量的网络上，平凡地，我们假设每次增广的流量都是整数，则 Ford–Fulkerson 增广的时间复杂度的一个上界是 ，其中 f 是最大流。这是因为单轮增广的时间复杂度是 O(E)，而增广会导致总流量增加，故增广轮数不可能超过 f。
对于 Ford–Fulkerson 增广的不同实现，时间复杂度也各不相同。其中较主流的实现有 Edmonds–Karp, Dinic等算法，我们将在下文中分别介绍。

Edmonds–Karp 算法

如何寻找增广路呢？当我们考虑 Ford–Fulkerson 增广的具体实现时，最自然的方案就是使用 BFS。此时，Ford–Fulkerson 增广表现为 Edmonds–Karp 算法。
显然，单轮 BFS 增广的时间复杂度是 ，增广总轮数的上界是 （证明略，实在想搞明白可以参考：最大流 - OI Wiki），所以总体时间复杂度是 。

Dinic 算法

考虑在增广前先对 做 BFS 分层，即根据结点 u 到源点 s 的距离 d(u) 把结点分成若干层。令经过 u 的流量只能流向下一层的结点 v，即删除 u 向层数标号相等或更小的结点的出边，我们称剩下的部分为层次图 ，其中 。
如果我们在层次图上找到一个最大的增广流 ，则称为 的阻塞流。
尽管在上文中我们仅在单条增广路上定义了增广/增广流，广义地，「增广」一词不仅可以用于单条路径上的增广流，也可以用于若干增广流的并——后者才是我们定义阻塞流时使用的意义。
定义层次图和阻塞流后，Dinic 算法的流程如下：
  1. 重复以上过程直到不存在从 s 到 t 的路径
在分析这一算法的复杂度之前，我们需要特别说明 DFS 的过程。尽管 BFS 层次图对于本页面的读者应当是 trivial 的，但 DFS 阻塞流的过程则稍需技巧——我们需要引入当前弧优化。
注意到在 DFS 的过程中，如果结点 u 同时具有大量入边和出边，并且 u 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则这个局部的时间复杂度最坏可达 。为避免这一缺陷，如果某一时刻我们已经知道边 (u,v) 已经增广到极限（已无剩余容量或 v 的后侧已增广至阻塞），则 u 的流量没有必要再尝试流向出边 v。据此，对于每个结点 u，我们维护 u 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。
多路增广是 Dinic 算法的一个常数优化（不会改变Dinic算法 的最坏情况时间复杂度，但可以显著减少常数因子）——如果我们在层次图上找到了一条从 s 到 t 的增广路 p ，则接下来我们未必需要重新从 s 出发找下一条增广路，而可能从 p 上最后一个仍有剩余容量的位置出发寻找一条岔路进行增广。考虑到其与回溯形式的一致性，这一优化在 DFS 的代码实现中也是自然的。
可能是由于大量网络资料的错误表述引发以讹传讹的情形，相当数量的选手喜欢将当前弧优化和多路增广并列称为 Dinic 算法的两种优化。实际上，当前弧优化是用于保证 Dinic 时间复杂度正确性的一部分，而多路增广只是一个不影响复杂度的常数优化。
完整代码如下：
单轮增广中 DFS 求阻塞流的时间复杂度是 ，增广轮数是 。
Dinic 算法在大部分图上效率非常优秀。背它就对了。

二分图最大匹配

给定一个二分图 G，即分左右两部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。
二分图最大匹配可以转换成网络流模型。将源点连上左边所有点，右边所有点连上汇点，容量皆为 1。原来的每条边从左往右连边，容量也皆为 1，最大流即最大匹配。
用 Dinic 算法解决，时间复杂度为 ，其中 m 为边数，n 为结点数。

练习题

P3376 【模板】网络最大流

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式：
第一行包含四个正整数 nmst，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来 m 行每行包含三个正整数 uiviwi，表示第 i 条有向边从 ui 出发，到达 vi，边权为 wi（即该边最大流量为 wi）。
输出格式：
一行，包含一个正整数，即为该网络的最大流。
直接调用上面写的模版类即可，注意这题结点编号从 1 开始，所以分配内存时需要多分一单位：
注意 python 的输入方式。Python 算法题常用输入输出方式总结如下：
控制台单行输入
多行输入
矩阵输入
常见输出方式
文件输入输出