最大流

给定一张 \(\text{DAG}\)，每条边有一个「容量」\(c\)。你需要找到从 \(S\) 到 \(T\) 的最大流。

FF算法

首先一开始对每条边建立一条容量为 \(0\) 的反向边。

然后每轮执行以下操作：

1. 在残量网络（即还能流的网络）中找到一条 \(S\) 到 \(T\) 的增广路。
2. 令 \(w=\) 增广路所有边剩余容量的最小值。则：

• \(ans+=w\)
• 增广路上所有边的剩余容量 \(-=w\)
• 增广路上所有反向边的剩余容量 \(+=w\)

举个典型的例子：

显然，最大流为2，就是上面一条和下面一条。但是我们的程序没有那么聪明，他有可能找出一条这样的路：

此时答案加一，然后进行反悔操作：

然后此时程序又找到了一条经过反向边的增广路，于是答案再加一：

然后就得到了想要的结果，因为这个方案跟我们的方案是本质一样的。

至于原理可以参考匈牙利算法。刚刚的反悔就相当于，寻找一个点的匹配时，是否可以换掉别人的匹配。

比如这张图中，第二条路径本来想要直接从下面到 \(T\)，但是那条边的流量已经满了。所以我们让原本在那里的水，沿着中间跨过来的边流回去。这个操作就等价于那个反悔操作。

那么不难看出， \(\text{FF}\) 算法就是一种很正确的带有反悔行为的策略。

不过众所周知，\(\text{DAG}\) 上的 \(\text{dfs}\) 是 \(\text{NP}\) 问题，根本没法跑啊 qwq。

EK算法

在 \(\text{FF}\) 算法上做一个“简单”的优化：每次找一条边数最少的增广路。即把 \(text{dfs}\) 换成了 \(\text{bfs}\)。快了一些！

分析一下时间复杂度。这里引入一个结论：增广总轮数的上界是 \(\mathcal{O}(nm)\)。证明不会qwq。想了解的请至 OI-Wiki。

Dinic算法

\(\text{EK}\) 算法每次找增广路都要跑一遍 \(\text{bfs}\)，是不是有点浪费了呀。。。毕竟我只想要一条路径。

\(\text{Dinic}\) 算法：用 \(bfs\) 来依次找距离 \(S\) 边数为 \(1,2,3,...,n\) 的点，然后每次走一下增广路。快了一些！

再次分析时间复杂度。还是那个结论，增广总轮数的上界是 \(\mathcal{O}(nm)\)。