Dinic算法

本文讲解Dinic算法的思路, 算法本身与证明。

关于残余网络增广路等概念的说明, 请看Ford-Fulkerson算法这篇文章。这里只致力于改进Ford-Fulkerson算法, 得到一个与$F$无关的算法。

问题

$F$较大时, 影响Ford-Folkerson算法效率的主要因素在于: 每次dfs可能可以找到许多条路径, 但是该算法中每次dfs只进行一次增广, 这就导致增广次数与$F$ (可能) 相关。一种想法是一次dfs多次增广, 但这样做能否成功是取决于dfs顺序的, 于是考虑, dfs顺序如何时, 效率较高呢?

思路

Dinic算法的核心是每次寻找最短的增广路, 并进行增广。这样做的理由 (既是依据, 也是好处) 是, 每次沿最短增广路增广后, 最短增广路的长度一定不会减少, 稍后会给出证明。假如有了这一结论, 每次找到最短增广路的长度时, 将该长度的增广路[全部增广], 然后重新寻找最短增广路, 其长度至少增1, 而增广路长度不会超过$|V|$ (因为增广路是简单路径) , 从而增广次数上界$O(|V|)$

证明

下面证明, 每次沿最短增广路增广后, 最短增广路的长度一定不会减少。在原图上, 为寻找最短增广路, 从$s$出发bfs, 设第一次到达点$v$的边为$\langle u,v\rangle$, 为点$v$编号$n_v=n_u+1$。由bfs的特性, 每条边增量 (指该边终点与起点编号差, 可为负值, 后均同) 不超过1。特别地, $n_s=0,s$为源点。称这个图为分层图

此时有结论: 若$n_t$被更新, 那么最短增广路的长度为$n_t$。为了证明, 可以寻找为$n_t$标号的边的出发点$i$, 再寻找为$i$标号的边的出发点$j$, …, 最终会回到$s$, 并且沿每条边标号增1。由于每条边增量不超过1, 每条边都增1是从0到$n_t$最快的方法, 从而我们找到了 (一条) 最短增广路$l_{min}$, 并且每个最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$

下面使用数学归纳法。

(1) 在分层图上沿最短增广路增广1次后, 新图中可能出现一些新的反向边。若新图中有增广路$l'$, 其中的边的来源有两种可能:

【1边】原分层图中的边 (bfs时经历过的边) $\langle u,v\rangle$, 满足$n_v\leq n_u+1$;

【2边】增广时出现的反向边$\langle v,u\rangle$, 记原边为$\langle u,v\rangle$, 那么由于原边在最短增广路中, 一定满足$n_v=n_u+1$

那么沿该路径中任何一条边编号增加不超过1, 为了从$0$到达$n_t$仍然至少需要$n_t$条边, 长度没有变短, 所以最短增广路长度没有减少, 并且所有边都仍满足$n_v\leq n_u+1$

(2) 假设沿最短增广路增广n次后, 最短增广路长度不减少。当增广$(n+1)$次后, 若图中无增广路, 结论成立。若图中仍有增广路, 其中的边可能是:

【1边】增广n次后的图中的边$\langle u,v\rangle$, 满足$n_v\leq n_u+1$;

【2边】第$(n+1)$次增广时出现的反向边$\langle v,u\rangle$, 记原边为$\langle u,v\rangle$, 那么由于原边在最短增广路中, 一定满足$n_v=n_u+1$

类似于上面, 可以证明沿最短增广路增广$(n+1)$次后, 最短增广路长度仍不减少, 并且所有边都仍满足$n_v\leq n_u+1$

综上, 沿最短增广路增广后, 最短增广路长度不会减少。

优化

首先, 在证明中我们知道: 最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$, 从而我们只考虑递增的边不会出现错误。实际上, 每次分层完后, 只要找到增广路就可以增广, 不必局限在最短增广路中增广, 这是自缚手脚。只考虑递增的边的情况下, 情况立刻不同了: 图成为了DAG! 从而, 边$\langle u,v\rangle$能否使用只与$v$可达的点 (记符合条件的点集为$V$, 那么$\forall g \in V$, $n_g>n_v$) 的情况有关, 而与$s$如何到达$u$无关, 从而, 如果某一时刻发现一条边不能使用, 那么在重新bfs (即重新标号) 之前, 无论其他地方如何增广, 其后的边流量只会减少不会增加, 这条边都仍然不能用来增广。于是可以记录这些边使之只遍历一次, 每次分层至多访问它们$O(|E|)$次。

算法描述

下面的算法只是大致的描述, 没有伪代码那么明确, 重在讲清楚过程, 希望我做到了。

(Dinic算法) 输入: 网络$G(V,E)$ 输出: 最大流$max\_flow$

步骤0. [准备]建立数组$iter[V]$, 定义$max\_flow\gets0$, 用邻接表$G[V]$存储网络;

步骤1. [建立分层图]bfs(s,0), 当bfs(u,n)时, 若$n_u$已定义, 返回; 否则记$n_u=n$, 并对$G[u]$中的所有元素$v$进行bfs(v, n+1)。清零$iter[]$数组。

步骤2. [有增广路吗? ]若$n_t$未定义, 退出算法, 返回$max\_flow$

步骤3. [寻找增广路]在$G$上DFS, 寻找从$s$$t$的简单路径, 要求该路径上每条边$e\langle u,v\rangle$可用权值$(w_e-f_e)$大于0, 并且$n_v>n_u$。若找到, 记该路径上的权值最小的边权值为$f$, 否则$f\gets0$。DFS(u)时按顺序遍历$G[u]$, 若$G[u][i]$不可用, $iter[u]\gets iter[u]+1$

步骤4. [找到了, 更新残余网络]如果$f>0$, 置$max\_flow\gets max\_flow+f$。对路径上的每条边$e$, 置$f_e\gets f_e+f$。记其反向边为$e'$, 置$w_{e'}\gets w_{e'}+f$。返回步骤3。

步骤5. [没有找到]如果$f=0$, 返回步骤1。

复杂度

由于每次dfs都至少使一条边满流 (从而使之无法使用) , dfs次数上界为$O(|E|)$。在当前弧优化后, 每次dfs经过的边有两种可能性: (1) 是无用边 (2) 在增广路里, 其中 (1) 无用边在一次分层内总共访问$O(|E|)$次, 而 (2) 成功增广的情况中, 增广路长度不超过$|V|$, 每次分层中情况 (2) 的总复杂度上界为$O(|E||V|)$, 从而每次分层的复杂度上界为$O(|E||V|+|E|)=O(|E||V|)$, 从而Dinic算法总的时间复杂度为$O(|E||V|^2)$

模板

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数, 视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge{
    ll to, w, rev;
};
vector<edge> G[V];
int num[V], iter[V];
int s, t;//源点和汇点, 是全局变量

ll max_flow();
ll dfs(ll u, ll f);
void bfs();
void add_edge(ll from, ll to, ll w);

ll max_flow() {
    ll f = 0, flow = 0;
    while(true) {
        memset(iter, 0, sizeof(iter));
        bfs();
        if(num[t] == -1) return flow;
        while(f = dfs(s, INF)) {
            flow += f;
        }
    }
}
ll dfs(ll u, ll f) {
    if(u == t) return f;
    ll flow;
    for(int &i = iter[u]; i < G[u].size(); i++) {
        edge &e = G[u][i];//注意是引用, 需要直接修改原图
        if(e.w > 0 && num[u] < num[e.to]) {
            if(flow = dfs(e.to, (f > e.w ? e.w : f))) {
                //min函数有些编译器不给过, 所以用三目
                e.w -= flow;
                //直接修改容量而非同时记录f和w, 只是为了方便
                G[e.to][e.rev].w += flow;
                return flow;
            }
        }
    }
    return 0;
}
void bfs() {
    memset(num, -1, sizeof(num));
    queue<int> que;
    que.push(s);
    num[s] = 0;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i < G[u].size(); i++){
            edge &e = G[u][i];
            if(e.w > 0 && num[e.to] < 0) {
                num[e.to] = num[u] + 1;
                que.push(e.to);
            }
        }
    }
}
void add_edge(ll from, ll to, ll w) {
    G[from].push_back(edge{to, w, G[to].size()});
    G[to].push_back(edge{from, 0, G[from].size() - 1});
}

如有发现模板的错误请联系我指正, 我将不胜感激。