最大流之 Dinic 算法

· · 算法·理论

今天要讲的是 Dinic 算法！之前我们讲过使用 EK 算法来解决最大流问题，可是还有没有优化的余地呢？就让我们来探究一下 Dinic 的奥妙之处。

前置知识：最大流之入门知识与原理 && 最大流之 Ford - Fulkerson 算法与 EK 算法。

问题引入

我们知道，EK 算法是在不断用最短路径贪心地寻找增广路，然而这样做有一个致命的缺点。请看这幅图：

点“……”代表许多许多点，我们暂且假设从点“^_^”到点“awa”的这一条长链的点的个数为 10^5。EK 会怎样解决这样一张图的网络流问题呢？

EK 的本质是 BFS。可以想象到，在执行 EK 算法时，会从源点经过非常长的一条链并选择一条“awa”->“T”的路径。接着，我们会继续尝试其他分支，并且每次都需要经过这个无比长的链！然后 EK 就像被耍了一样，发现每次更新的答案都一样……如果汇点处的分支更多，时间复杂度将会超乎想象，因为每个分支都会让 BFS 经过一次这一条链。

相信你很快就发现了 EK 的缺陷：每次都重新搜，容易把一堆东西重复搜。怎么优化呢？我们想到：DFS 可以回溯，我们可以让 DFS 一次性搜索完一堆点而不用重新从源点开始搜！但是我们需要一种高效的 DFS 方法，否则将会退化为纯暴搜 Ford - Fulkerson 呀。

于是现在给出一种限制方法：分层。我们先通过 BFS 将网络分层，离源点越近，层数越小；离源点越远，层数越大。在 DFS 时，我们规定只能从前一层搜向后一层。这样就不能让同层的点互相搜了，同时也在步步逼近汇点，是不是限制住了“乱搜”的 DFS？在一次 DFS 结束后，我们就继续用 BFS 重新分层，直到再也分不了为止。如此一来，我们就完成了初步的算法框架设计。

代码实现

代码分为 BFS，DFS 和 Dinic 三个函数。

Dinic 函数的实现

Dinic 函数是主要的执行函数，代码短，结构简单。

Dinic 算法的本质依然是不断地寻找增广路。在函数中，我们不断地 BFS 直到源点和汇点不连通。BFS 是 DFS 中找增广路的铺垫。因此，BFS 和 DFS 函数都不只会执行一次。将所有 DFS 中找到的增广流量加起来，就是答案。

ll dinic() {
    ll maxflow = 0;
    while (bfs()) maxflow += dfs(s, 1e18);
    // 我们可以暂时不用看bfs和dfs中的参数
    return maxflow;
}

我们可以通过 Dinic 函数大致了解最大流的框架。

BFS 函数的实现

我们定义 level_i 为点 i 的层数，level 的初始值为 0。注意，源点的层数必须设为 1 而不能设为 0，因为我们此时的 level 数组也充当了标记数组 vis 的作用，level_i=0 就代表点 i 没有被访问。level 的值是逐层递进的，也就是下一个点的 level_{nxt}=level_{pre}+1。

值得注意的是，如果一条边的剩余流量为 0，也就是不能再流通了，那么我们就不能经过这条边，否则分层就没有意义了。

具体实现如下，可以仔细阅读注释理解。

int level[N];
// 定义我们所需要的变量，数组
bool bfs() { // bfs函数的主要作用是：分层
    fill(level + 1, level + 1 + n, 0); // 初始化为0
    queue<int> q; // 定义队列
    q.push(s); 
    level[s] = 1; // 源点的level值必须设为1
    while (!q.empty()) {
        ll cur = q.front(); q.pop();
        for (ll i = 0; i < nbr[cur].size(); i++) if (!level[nbr[cur][i].to] && nbr[cur][i].w) {
            // 没有标记过并且这条边有流量（不然每次的分层结果都一样了呀）
            ll nxt = nbr[cur][i].to, w = nbr[cur][i].w;
            q.push(nxt); // 将新的点存入队列，继续bfs 
            level[nxt] = level[cur] + 1; 
            if (nxt == t) return 1; // 如果已经到达了汇点，就可以结束了 
        }
    }
    return 0; // 否则bfs失败 
}

是不是很简单？我们可以发现，BFS 函数的返回值是 bool 类型的，这个返回值代表着当前的网络中源点和汇点是否连通。如果源点都流不到汇点了，那么也就不可能再有新的流量（增广路）了。

DFS 函数的实现

DFS 函数当然符合普通 DFS 的结构。我们来逐一攻破：

  1. 边界条件

    如果当前已经到达了汇点，就成功找到了一条增广路。此时我们需要返回当前的流量。

  2. 递归调用

    当 DFS 函数执行到点 cur 时，假设来到点 cur 的有 flow 的流量。接下来需要分流。也就是说，对于每个 cur 的邻接点，都需要将一些流量分给这些点。同时，不能违背了之前的约定：下一个邻接点必须比 cur 的层数严格大 1，也就是不能在同一层中搜索，否则就又退化为 Ford - Fulkerson 算法了。此时 cur\to nxt 的有向边的剩余流量不能为 0，与 BFS 同理。

    我们会在分流的过程中将 flow 分出去，所以 cur 点的剩余流量在不断减少。我们将当前剩余的流量设为 rest，初始时 rest=flow。那么递归到下一个点 nxt 时，nxt 有多少流量能从边 cur\to nxt 流出呢？这取决于当前我有多少流量和 cur\to nxt 这条边的流量上限，那么流过去的流量就是这两个值之中较小者的值。若 cur\to nxt 这条边的流量上限为 w，那么在点 nxt 处就有 flow_{nxt}=\min(rest,w)。如果在某一时刻 rest=0，那么接下来的点就都没有流量可分了，可以直接跳出循环。这是第一个剪枝。

    接着，递归结束的点 nxt 带来的返回值是什么呢？当然是 nxt 这条分支最后到汇点的流量啦！在 nxt\to T（T 是汇点）的路径中，流量有可能越来越小，此时我们将最后 nxt\to T 的流量设为 inc。若 inc=0，没有流量，那么从 nxt 处找不到增广路，在这一次增广中也不可能再找到了。于是，我们可以让所有点都不再经过这个点，也就是令 level_{nxt}=0。这是第二个剪枝。

  3. 回溯处理

    我们知道，在 EK 算法中，有一个重要的步骤：更新网络。我们在找到一条增广路后，一定要减少正向边的流量并增加对应的反向边的流量。但在 Dinic 算法中，由于算法本身就是用 DFS 实现的，所以这项操作本能地非常容易实现，在 DFS 中直接加减流量就可以了，回溯时自然会找到一条路径。同时，我们要记得更新 rest，rest\gets rest-inc（\gets 表示赋值），也就是 rest 要减去 inc。

  4. 返回值处理

    那么，函数最后的返回值是什么呢？换句话说，点 cur 到底流出了多少流量？显然是 flow-rest。比如一开始有 100 的流量，最后流啊流只剩 10 的流量没有流出去，那么就流出去了 (100-10=90) 的流量。

相信你看了这么多后，脑袋是晕乎乎的。没错，这个时候就要配合代码食用！！

ll dfs(ll cur, ll flow) { // dfs函数的主要作用是：找增广路
    if (cur == t) return flow; // 如果到了汇点，就不用继续往下走了
    ll rest = flow; // rest记录剩下的流量
    for (ll i = 0; i < nbr[cur].size() && rest; i++) { // “&& rest” 就是我们提到的第一个剪枝
        ll nxt = nbr[cur][i].to, w = nbr[cur][i].w;
        if (w && level[nxt] == level[cur] + 1) { // 这条边有流量且层数严格递增
            ll inc = dfs(nxt, min(rest, w)); // 递归调用，inc就是点nxt出最终流到汇点的流量
            if (!inc) level[nxt] = 0; // 这是第二个剪枝
            nbr[cur][i].w -= inc; 
            nbr[nxt][nbr[cur][i].bk].w += inc;
            // 直接在dfs中更新网络
            rest -= inc; // 别忘了rest
        }   
    }
    return flow - rest; // 流出的流量等于最初的流量减去最后的流量
}

复杂度分析

时间复杂度：\Theta(n^2m)。

证明比较复杂，咱们不需要太过深入了解~

与 EK 算法的比较

直观上看，Dinic 和 EK 的复杂度似乎没有差得太多。然而实际上，Dinic 算法在一般情况下都比 EK 算法要快！这是因为边的数量 m 可能会很大，最多达到 n^2 级别，那么 Dinic 算法的时间复杂度 \approx\Theta(n^4)，EK 算法的时间复杂度 \approx\Theta(n^5)，差距还是挺大的。

不过有些人认为 EK 算法代码更短，更好写，不容易出错。那么究竟什么时候 EK 算法效率更优呢？答案是：层数较小的图。比如二分图最大匹配问题，我们知道可以通过设置超级源点和超级汇点并使用最大流解决。此时整张图只有 4 层：

此时 EK 算法的贪心可以很快找到一条增广路，那么就能快速更新答案。在实际做题时，我们也会遇到很多建模如上图的题，此时用 EK 算法较好；否则，还是用 DInic 算法比较谨慎，不然容易超时。

例题

主要是要把模板重新打一遍，增强熟练度，尽量排除一些容易犯的错误。在刚学习 Dinic 后，一定不要复制模板，要自己老老实实打！

后面的两道题作为挑战，可以先思考一下，会在后面的习题篇里详细讲解。

当前弧优化

想象一下，如果在多次增广后一些边的流量已经是 0 了，BFS 也不会搜索到了，那么就完全没有必要考虑。可是我们在枚举邻接点的时候，就会在这些已经增广过的边上浪费时间。比如这幅图：

如果 1\sim10^4 的所有点都已经被增广完了（剩余流量为 0），那么下次枚举的时候就需要再次枚举所有 1\sim10^4 的点，从 10^4+1 开始才是有效操作。于是，我们可以记录一个值，代表当前已经增广到了哪里，那么这个值之前的所有点就都不可能被增广。我们把这个值记作 tmp_x，那么我们枚举邻接点的时候从 tmp_x 开始枚举就好了。

核心代码改动有两处：

这样就可以进一步优化我们的运行效率了。

后记

这一篇文章是 Dinic 算法的介绍与入门，希望能对你有帮助。后面还打算补一个习题篇，毕竟最大流题目的解题技巧比光秃秃的模板还是更重要。希望你能好好消化这些知识，那我们下次再见！