网络最大流-从入门开始，详细讲到实用易懂的Dinic算法

*2022-10-10 更新：当前弧优化* # 理解网络 一张网络，是一张带权有向图。比喻成**输水系统**可能好理解—— 源头是大水库，想输出多少就输出多少。 但是，想要输出到目的地，需要经过中转点。中转点不产生新流量、也不私吞；**接受多少流量，就同时输出多少流量**。 点与点之间管道的容量（可以理解为水流量限制；注意“流量”指单位时间通过量，可以想象一下）是有限的；一条边上的流量不能超出其容量，**容量很可能是有残余的**。因为这些边上的限制，源头并不能无限输出。  于是有的人就想要求出：这张网络运作起来的时候，总流量最大能有多少。由于容量限制比较复杂，似乎不容易规划一个最佳方案。 下面来了一张经典图和一只猴子。  边上的数字是其容量限制。  红色的路径，是猴子随便添加的一条可行流（电脑不能看见整张图，所以它跟猴子没啥区别）。这个时候总流量是 $1$。 然后猴子继续随机尝试。想要让水流通过下方的黑边，但接下来没法把这份流量传到 $T$。猴子决定吃水果去了。 现在水正在按照红色路径流动，流量只有 $1$，就没法操作了。但你凭借聪明才智，很容易发现这是一种糟糕的策略，只要开始的时候 $S$ 沿着上下两条路走到 $T$，总流量就有 $2$ 了。 机智的猴子决定回来暴搜所有流法，它能解决这种规模的数据就已经很满意了……当然我们有更好的方法： **在水顺着管子流过去的时候，添加一条反向边，边的容量等于此次流量，允许其它路径过来。** 这个操作的正确性不太好理解。  想象红色管子里这个水正在咕咕流动，就这个方向。图中也标出了它们对应的反向边。 这时候**再次尝试找路**。$S$ 顺着下方管道给 $b$ 传过去 $1$ 流量。然后呢？$b$ 就找到了一条流到 $a$ 的反向边？这对吗？ 你可以理解成 $b$ 流回 $a$，也可理解为 $a$ 的反悔。  以**点**为主体进行考虑。$a$ 看到源点向 $b$ 给予 $1$ 流量，于是 $a$ 决定**收回它给予的等量流量，拿去做别的事情**。注意这时候我们再添加一条从 $a$ 到 $b$ 的反向边，相当于管道回到原先状态。也即对于中间的边，$a$ **不进行输出**。接下来 $a$ 只要找到新输出路径，早先的流量并没有被破坏。 总体来看，从源点开始，顺着有流量的边，只要能找到一条能到达汇点的路，就会使网络总流量增加，这种路叫**增广路**。经过上面两次增广，我们发现此图网络就没有增广路了。这样就一定找到最大流了吗？ ___ # 证明和写法 对一张网络，**是不是只要不断找增广路**（且增广过程中提供退回操作的机会）**，直到找不到，就是网络最大流？** 不好意思，这是真的。以下分两部分证明。当然平时做题不需要证明。 ## Part 1 假设一个网络正在流动。 现在任意割断一些边，把原来的点，分成不相连的两个点集，包括源点所在的点集，叫做 $S$，汇点所在的叫做 $T$。（只是为了分成两个点集，即**为了构成割**，才进行一下形式上的割断） 对于那张网络，除了源点和汇点，其它点都是“流入多少，就流出多少”，没有实际贡献或收入。 那么 $T$ 输出到汇点的流量哪儿来的呢？只能是 $S$ 给的；$S$ 则是源点给的。 原本 $S$ 到 $T$ 那几条边，它们的净流量称为 $S$ 到 $T$ 的净流量，（注意，也可能有边从 $T$ 流向 $S$，它们对净流量是负贡献） * $S$ 到 $T$ 的净流量 = 源点输出 = 汇点收入 = 网络总流量 不管怎么构造割，都有这个结果： * 图上任何一种割的净流量 = 网络总流量 因为割的净流量不可能超过割本身的容量（当然啦），所以， * 网络总流量 <= 图上任何一种割的容量 ## Part 2 经过猴子的调整，它的网络上没有增广路了。源点顺着残量网络到不了汇点了。 源点顺着残量网络能够到达的点，叫做点集 $S$（至少包含自己啊），剩下所有不能到达的点，叫做点集 $T$。则 $S$ 连向 $T$ 的边都没有残余容量（如果有残量边，$S$ 也顺着这条边包含了对面的点）。 如果把 $S$ 和 $T$ 中间的边割断，那么**这个割的净流量 = 这个割的容量**（因为边上都没有残余容量了）。 又因为 Part 1 证的“网络总流量 = 任意一个割的净流量”，所以**网络总流量 = 此割的容量（①）**。 其实这很不容易做到的，因为 Part 1 证了“网络总流量 <= 图上任何一种割的容量”，所以**“①”一定是面这个不等式的交界处。**  所以，这个网络流已经是众望所归。 一个总体的印象是：只要没有增广路，顺着残量网络到不了汇点，就存在一个无残量的割，其净流量等于容量；因为网络总流量同时等于图上任何一个割的净流量，也就同时绝不会超过图上任何一个割的容量，所以当总流量 = 某割的容量时，没有比它更大的流，分号以前达到了这个条件，所以现在是最大流。 （上面顺便证明了最大流 = 最小割） 准备开始：不断找增广路！ 你不用担心大量反向边会到导致死循环，因为每次找到增广路都会使流量增加，有限次增广一定能达到最大值。 实现起来也有很多细节和技巧。下面展示暴力算法，该算法效率低所以过不了模板，只能帮助你理解 Dinic。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 10010, E = 200010; int n, m, s, t; LL first[N]; LL to[E], nxt[E], val[E]/*残余容量*/; int cnt = 1; //cnt初值1，第一条边的标号为2（二进制10），第二条是3（二进制11） //有啥好处呢？ //我们加入一条边时，紧接着加入它的反向边（初始容量0） //这两条边的标号就是二进制最后一位不相同，一个0、一个1 //所以要召唤 p 这条边的反向边，只需用 p ^ 1 //如果cnt初值为0，就做不到。当然初值-1也可以，略需改动 //关于图中真正的反向边，可能引起顾虑，应该让它们标号相邻？ //其实不用。该找到的增广路都会找到的 bool vis[N];//限制增广路不要重复走点，否则很容易爆栈 //兜一大圈走到汇点，还不如直接走到汇点 void addE(int u, int v, LL w) { ++cnt; to[cnt] = v; val[cnt] = w; nxt[cnt] = first[u]; first[u] = cnt; } LL dfs(int u, LL flow) { //注意，在走到汇点之前，无法得知这次的流量到底有多少 if (u == t) return flow;//走到汇点才return一个实实在在的流量 vis[u] = true; for (int p = first[u]; p; p = nxt[p]) { int v = to[p]; if (val[p] == 0 or vis[v])//无残量，走了也没用 continue; int res = 0; if ((res = dfs(v, min(flow, val[p]))) > 0) { //↑顺着流过去，要受一路上最小容量的限制 val[p] -= res;//此边残余容量减小 val[p ^ 1] += res;//以后可以顺着反向边收回这些容量，前提是对方有人了 return res; } } return 0;//我与终点根本不连通（依照残量网络），上一个点不要信任我 } int main() { scanf("%d %d %d %d", &n, &m, &s, &t); for (int i = 1; i <= m; ++i) { int u, v; LL w; scanf("%d %d %lld", &u, &v, &w); addE(u, v, w); addE(v, u, 0);//和正向边标号相邻 //反向边开始容量为0，表示不允许平白无故走反向边 //只有正向边流量过来以后，才提供返还流量的机会 } LL res = 0, tot = 0; while (memset(vis, 0, sizeof(vis)) and (res = dfs(s, 1e18/*水库无限*/)) > 0) tot += res;//进行若干回合的增广 printf("%lld\n", tot); return 0; } ``` 这种直接深搜找增广路的办法叫做 FF。  由于**每次只找一条路，这条路还可能绕远路（可能经过 n 个点才到达汇点），而且增加流量是路上最小的权值**，效率低。网上有些题解试图简单卡 FF。  虽然这种图卡不掉 FF，你可以看出，FF 的复杂度和流量有关，这很糟糕。 下面的 Dinic 可解决 FF 效率低的问题。 * 每次多路增广：u 点通过一条边，向 v 输出流量以后，v 会尝试到达汇点（到达汇点才真正增广），然后 v 返回实际增广量。这时，**如果 u 还有没用完的供给，就继续尝试输出到其它边。** 但是要警惕绕远路、甚至绕回的情况，不加管制的话极易发生。怎么管？ * 源点**顺着残量网络**想要到达其它点，需要经过一些边对吧？**按照经过的边数（即源点出发以后的距离）把图分层，即用 bfs 分层。** 每次尝试给予时，**只考虑给予自己下一层的点**，就可以防止混乱。 * 综合上面两条。每回合也是从源点出发，**先按照当前残量网络分一次层**，随后多路增广，尽可能增加流量。增广过程中，会加入一些反向边，这些反向边逆着层次图，本回合并不会走。所以还需要进入下一回合。一直到 bfs 分层时搜不到汇点（即残量网络断了）为止。 这是 Dinic 算法。如果懂 FF，这个算法也很块能懂。 可是它每次只按照 bfs 分层的固定方向进行增广，还能保证正确性吗？这个好理解：只要图中还有增广路（源点顺着残量网络到达汇点的路），**bfs 分层就会搜索到汇点**，于是增广就不会停止，最终也止于没有增广路的局面。 关于**当前弧优化**的讨论，见代码下方。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 10010, E = 200010; int n, m, s, t; LL ans = 0; LL val[E]; int cnt = 1, first[N], nxt[E], to[E]; inline void addE(int u, int v, LL w) { to[++cnt] = v; val[cnt] = w; nxt[cnt] = first[u]; first[u] = cnt; } int dep[N], q[N], l, r; bool bfs() { //顺着残量网络，方法是 bfs；这是个bool型函数，返回是否搜到了汇点 memset(dep, 0, (n + 1) * sizeof(int)); //记得开局先初始化 q[l = r = 1] = s; dep[s] = 1; while (l <= r) { int u = q[l++]; for (int p = first[u]; p; p = nxt[p]) { int v = to[p]; if (val[p] and !dep[v]) { //按照有残量的边搜过去 dep[v] = dep[u] + 1; q[++r] = v; } } } return dep[t]; // dep[t] != 0，就是搜到了汇点 } LL dfs(int u, LL in /*u收到的支持（不一定能真正用掉）*/) { //注意，return 的是真正输出的流量 if (u == t) return in; //到达汇点是第一个有效return LL out = 0; for (int p = first[u]; p and in; p = nxt[p]) { int v = to[p]; if (val[p] and dep[v] == dep[u] + 1) { //仅允许流向下一层 LL res = dfs(v, min(val[p], in) /*受一路上最小流量限制*/); // res是v真正输出到汇点的流量 val[p] -= res; val[p ^ 1] += res; in -= res; out += res; } } if (out == 0) //我与终点（顺着残量网络）不连通 dep[u] = 0; //上一层的点请别再信任我，别试着给我流量 return out; } int main() { scanf("%d %d %d %d", &n, &m, &s, &t); for (int i = 1; i <= m; ++i) { int u, v; LL w; scanf("%d %d %lld", &u, &v, &w); addE(u, v, w); addE(v, u, 0); } while (bfs()) ans += dfs(s, 1e18); printf("%lld\n", ans); return 0; } ``` ### 当前弧优化 常见的“Dinic 当前弧优化”是错误的。 许多人误以为 dfs 遍历边的过程中有一个优化，即认为当一个点遍历到某一条边时，它之前的边必然已经增广完毕。这类优化在 dfs 中的遍历边会这样写： ```cpp for (int p = cur[u]; p and in; p = nxt[p]) { cur[u] = p; // 当前弧优化 int v = to[p]; if (val[p] and dep[v] == dep[u] + 1) { //仅允许流向下一层 LL res = dfs(v, min(val[p], in) /*受一路上最小流量限制*/); // res是v真正输出到汇点的流量 val[p] -= res; val[p ^ 1] += res; in -= res; out += res; } } ``` 但这是一个负优化！当我们遍历完 $cur[u]$ 之前的边，**仅仅意味着**从上一层某一个点走过来的路径无法再增广，然而在当前分层下，这个点可能从上一层另一个点走过来继续增广。这个优化将会推迟一部分增广到后一次分层。 实践：  $158ms$ 为加了“当前弧优化”的评测，而 $86ms$ 为不加该优化的评测。 注意理解多路增广：虽然一个点要枚举所有出边，但**实质仍然是 dfs**，过程图类似于树。  还有更快的算法参见预流推进，但网络流题目可能主要考察建模能力。 ___ 更新： 2019-03-30 代码和其中的注释修改。 2020-02-01 换图床，改句子。 2020-02-02 换图床。 2020-10-10 哇换了数据怎么不艾特一下。