学委
2018-12-28 21:29:43
2022-10-10 更新：当前弧优化
一张网络，是一张带权有向图。比喻成输水系统可能好理解——
源头是大水库，想输出多少就输出多少。
但是，想要输出到目的地，需要经过中转点。中转点不产生新流量、也不私吞；接受多少流量，就同时输出多少流量。
点与点之间管道的容量（可以理解为水流量限制；注意“流量”指单位时间通过量，可以想象一下）是有限的；一条边上的流量不能超出其容量，容量很可能是有残余的。因为这些边上的限制，源头并不能无限输出。
于是有的人就想要求出：这张网络运作起来的时候，总流量最大能有多少。由于容量限制比较复杂，似乎不容易规划一个最佳方案。
下面来了一张经典图和一只猴子。
边上的数字是其容量限制。
红色的路径，是猴子随便添加的一条可行流（电脑不能看见整张图，所以它跟猴子没啥区别）。这个时候总流量是
然后猴子继续随机尝试。想要让水流通过下方的黑边，但接下来没法把这份流量传到
现在水正在按照红色路径流动，流量只有
机智的猴子决定回来暴搜所有流法，它能解决这种规模的数据就已经很满意了……当然我们有更好的方法：
在水顺着管子流过去的时候，添加一条反向边，边的容量等于此次流量，允许其它路径过来。 这个操作的正确性不太好理解。
想象红色管子里这个水正在咕咕流动，就这个方向。图中也标出了它们对应的反向边。
这时候再次尝试找路。
你可以理解成
以点为主体进行考虑。
总体来看，从源点开始，顺着有流量的边，只要能找到一条能到达汇点的路，就会使网络总流量增加，这种路叫增广路。经过上面两次增广，我们发现此图网络就没有增广路了。这样就一定找到最大流了吗？
对一张网络，是不是只要不断找增广路（且增广过程中提供退回操作的机会），直到找不到，就是网络最大流？
不好意思，这是真的。以下分两部分证明。当然平时做题不需要证明。
假设一个网络正在流动。
现在任意割断一些边，把原来的点，分成不相连的两个点集，包括源点所在的点集，叫做
对于那张网络，除了源点和汇点，其它点都是“流入多少，就流出多少”，没有实际贡献或收入。
那么
原本
不管怎么构造割，都有这个结果：
因为割的净流量不可能超过割本身的容量（当然啦），所以，
经过猴子的调整，它的网络上没有增广路了。源点顺着残量网络到不了汇点了。
源点顺着残量网络能够到达的点，叫做点集
如果把
又因为 Part 1 证的“网络总流量 = 任意一个割的净流量”，所以网络总流量 = 此割的容量（①）。
其实这很不容易做到的，因为 Part 1 证了“网络总流量 <= 图上任何一种割的容量”，所以“①”一定是面这个不等式的交界处。
所以，这个网络流已经是众望所归。
一个总体的印象是：只要没有增广路，顺着残量网络到不了汇点，就存在一个无残量的割，其净流量等于容量；因为网络总流量同时等于图上任何一个割的净流量，也就同时绝不会超过图上任何一个割的容量，所以当总流量 = 某割的容量时，没有比它更大的流，分号以前达到了这个条件，所以现在是最大流。
（上面顺便证明了最大流 = 最小割）
准备开始：不断找增广路！
你不用担心大量反向边会到导致死循环，因为每次找到增广路都会使流量增加，有限次增广一定能达到最大值。
实现起来也有很多细节和技巧。下面展示暴力算法，该算法效率低所以过不了模板，只能帮助你理解 Dinic。
#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 分层就会搜索到汇点，于是增广就不会停止，最终也止于没有增广路的局面。
关于当前弧优化的讨论，见代码下方。
#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 中的遍历边会这样写：
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;
}
}但这是一个负优化！当我们遍历完
实践：