「算法笔记」网络流 - 最大流

最大流,指一张网络图中的最大流量。


网络流系列文章

  1. 最大流
  2. 最小割
  3. 费用流
  4. 上下界网络流

概念

网络流

网络流是指给定一个有向图,其中有两个特殊的点:源点 $s$(Source)和汇点 $t$(Sink);每条边都有一个指定的流量上限,下文均称之为容量(Capacity),即经过这条边的流量不能超过容量,这样的图被称为网络流图。同时,除了源点和汇点外,所有点的入流和出流都相等,源点只有流出的流,汇点只有流入的流,网络流就是从 $s$ 到 $t$ 的一个可行流

可行流

定义 $c(u,v)$ 表示边 $(u,v)$ 的容量,$f(u,v)$ 表示边 $(u,v)$ 的流量。如果满足 $0\le f(u,v)\le c(u,v)$,则称 $f(u,v)$ 为边 $(u,v)$ 上的流量。

如果有一组流量满足:源点 $s$ 的流出量等于整个网络的流量,汇点 $t$ 的流入量等于整个网络的流量,除了任意一个不是 $s$ 或 $t$ 的点的总流入量等于总流出量。那么整个网络中的流量被称为一个可行流。

最大流

在所有可行流中,最大流指其中流量最大的一个流的流量。


定义

我们定义(部分定义在上文有涉及):

  • 源点 $s$:只有流出量的点。
  • 汇点 $t$:只有流入量的点。
  • 容量 $c$:$c(u,v)$ 表示边 $(u,v)$ 上的容量。
  • 流量 $f$:$f(u,v)$ 表示边 $(u,v)$ 上的流量。
  • 残量 $w$:$w(u,v)$ 表示边 $(u,v)$ 上的残量(显然有 $w(u,v)=c(u,v)-f(u,v)$)。

性质

容量限制

对于任何一条边,都有 $0\le f(u,v)\le c(u,v)$。

斜对称性

对于任何一条边,都有 $f(u,v)=-f(v,u)$。即从 $u$ 到 $v$ 的流量一定等于从 $v$ 到 $u$ 的流量的相反数。

流守恒性

对于任何一个点 $u$,如果满足 $u\neq s$ 并且 $u\neq t$,那么一定有 $\sum f(u,v)=0$,即 $u$ 到相邻节点的流量之和为 $0$。因为 $u$ 本身不会制造和消耗流量。


求解

増广路

网络流的所有算法都基于増广路的思想,接下来首先介绍一下増广路思想。

  1. 找到一条从 $s$ 到 $t$ 的路径,使得路径上的每一条边都有 $w(u,v)>0$ 即残量大于 $0$。注意:这里是严格 $>$ 而不是 $\ge$,这意味着这条边还可以分配流量。这条路径就被叫做増广路。
  2. 找到这条路径上最小的 $w(u,v)$,记为 $flow$。将这条路径上的每一条边的 $w(u,v)$ 减去 $flow$。
  3. 重复上述过程,直到找不到増广路为止。

注意:其实上述方法并不是正确的,但这是一个非常重要的分析过程,因此请读者仔细阅读!

我们可以根据这个过程在下面这张图中模拟一遍。

如果我们把每条边的的信息用残量 / 容量表示出来,可以得到下图:

假设我们第一次找到的増广路为 $1-2-3-4$,那么我们把这条路径上的边的 $w(u,v)$ 减去 $\min\{f(u,v)\}$ 即 $1$,得到下图:

然后呢……我们发现已经没有増广路了,此时算出来的“最大流”为 $1$!但是我们可以手动计算一下,这张图的最大流其实是 $2$!这个最大流的路径为 $1-2-4$(流量为 $1$)和 $1-3-4$(流量为 $1$)。

因此,我们可以发现这样的过程是错误的。原因就是増广路在一定意义上是有顺序的,说白了就是没有给它反悔的机会。所以我们要引入反向边的概念。

反向边

改进

通过上文的分析我们已经知道,当我们在寻找増广路的时候,找到的并不一定是最优解。如果我们对正向边的 $w(u,v)$ 减去 $flow$ 的同时,将对应的反向边的 $w(v,u)$ 加上 $flow$,我们就相当于可以反悔从这条边流过。

那么我们可以建立反向边,初始时每条边的 $w(u,v)=c(u,v)$,它的反向边的 $w(v,u)=0$(显然反向边不能有流量,因此残量为 $0$)。

接下来再看一下上面那个例子,我们只用 $w(u,v)$ 来表示每条边(包括反向边)的信息:

接下来开始寻找増广路,假如还是 $1-2-3-4$ 这条路径。

我们需要把 $w(1,2)$,$w(2,3)$,$w(3,4)$ 减少 $1$,同时把反向边的 $w(2,1)$,$w(3,2)$,$w(4,3)$ 增加 $1$。那么可以得到下图:

继续从 $s$ 开始寻找増广路(不需要考虑边的类型),显然可以发现路径 $1-3-2-4$,其中 $flow=1​$。更新边的信息,得到下图:

此时我们发现没有増广路了,为了直观观察这个网络,我们去掉反向边,显然我们求出的最大流为 $2$!

正确性

当我们第二次増广边 $(2,3)$ 走这条反向边 $(3,2)$ 时,把 $(2,3)$ 和 $(3,2)$ 的流量抵消了,相当于把 $(2,3)$ 这条正向边的流量给退了回去使得可以不走 $(2,3)$ 这条边。

如果反向边 $(v,u)$ 的流量不能完全抵消正向边 $(u,v)$,那么意味着从 $u$ 开始还可以流一部分流量到 $v$,这样也是允许的。

小技巧

如何快速找到反向边?如果使用邻接表存图,那么可以对边从 $2$ 开始编号,那么下标为 $i$ 的边的反向边就是 $i\ \text{XOR}\ 1$。

思路总结

  1. 最初这个网络的流量为 $0$,称为零流
  2. 找到一条从 $s$ 到 $t$ 的路径,使得路径上的每一条边都有 $w(u,v)>0$ 即残量大于 $0$。注意:这里是严格 $>$ 而不是 $\ge$,这意味着这条边还可以分配流量。这条路径就被叫做増广路。
  3. 找到这条路径上最小的 $w(u,v)$,记为 $flow$。
  4. 将这条路径上的每一条边的 $w(u,v)$ 减去 $flow$,同时将反向边 $(v,u)$ 的 $w(v,u)$ 加上 $flow$。
  5. 重复上述过程,直到找不到増广路为止,此时的流量就是最大流。

这个算法基于増广路定理:网络达到最大流当且仅当残留网络中没有増广路。然而我不会证明 QAQ


算法

求最大流有若干种算法,此处介绍其中的两种:$\text{Edmonds-Karp}$ 和 $\text{Dinic}$。

Edmonds-Karp

实现过程

简称 $\text{EK}$ 算法,每次用 $\text{BFS}$ 求出一条増广路径,通过记录每个点的前驱和这条边的编号来记录下这条路径。可以说是对増广路思路的完全模拟。

但是 $\text{EK}$ 在某些情况下会被卡得很慢。假如有下面这张图:

其中 $w(u,v)=1$,其余正向边的 $w(u,v)=100$。如果第一次増广路的策略不恰当,找到了 $1-2-3-4$,那么 $w(2,3)=0$,$w(3,2)=1$。接下来又会找到増广路经 $1-3-2-4$,然后又是 $1-2-3-4$……

然后显然最大流路径就是 $1-2-4$(流量为 $100$)和 $1-3-4$(流量为 $100$),但是如果策略不当,就会这样不断这样増广下去,导致复杂度会爆炸!

复杂度

$\text{EK}$ 算法的时间复杂度为 $\mathcal O(nm^2)$。我们可以证明最多需要 $\mathcal O(nm)$ 次増广可以达到最大流,每次増广的复杂度为 $\mathcal O(m)$。绝大多数情况下这个复杂度都跑不满。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 2e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, s, t;
int tot = 1, lnk[N], ter[M], nxt[M], cap[M], pre[N], idx[N];
bool vis[N];

void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs(int s, int t) {
    memset(pre, 0, sizeof(pre));
    memset(vis, 0, sizeof(vis));
    std::queue<int> q;
    q.push(s), vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (!vis[v] && cap[i]) {
                pre[v] = u, idx[v] = i, q.push(v), vis[v] = 1;
                if (v == t) return 1;
            }
        }
    }
    return 0;
}
int EK(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int mn = INF;
        for (int i = t; i != s; i = pre[i]) {
            mn = std::min(mn, cap[idx[i]]);
        }
        for (int i = t; i != s; i = pre[i]) {
            int x = idx[i];
            cap[x] -= mn, cap[x ^ 1] += mn;
        }
        ans += mn;
    }
    return ans;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
    }
    printf("%d\n", EK(s, t));
    return 0;
}

Dinic

实现过程

我们发现 $\text{EK}$ 在某些情况下会很低效,我们有另一个算法 $\text{Dinic}$。它引入了分层图的概念,具体的方法如下:

  1. 为了避免走重复的路径,从 $s$ 开始 $\text{BFS}$ 对图分层,将整个图分为若干层,其中 $s$ 是第 $1$ 层。如果一条边的残量为 $0$,那么忽略这条无法増广的边。如果 $t$ 的层数不为 $0$,那么意味着存在増广路径。
  2. 如果存在増广路,那么从 $s$ 开始进行 $\text{DFS}$ 寻找从源点到汇点的増广路,注意此处増广必须要按照图的层次来遍历。每次下传当前流量 $flow$(初始流量认为是无穷大)。

设 $dep_i$ 表示 $i$ 的层次,$ans$ 代表当前从 $u$ 可以流的流量,对于当前点 $u$ 相连的点 $v$,如果 $dep_v=dep_u+1$ 并且 $w(u,v)>0$,那么可以増广。此时下传的 $flow$ 应为 $\min(w(u,v),flow-ans)$,其中 $flow-ans$ 代表从 $u$ 还可以流的流量(已经有 $ans$ 的流量从 $v'$ 流出去了)。当 $ans\ge flow$ 时意味着没有可以流的流量了,应该退出増广

如果该 $\text{DFS}$ 找到的可以増广的流量为 $0$,表示增广失败,跳过这条边。否则将 $w(u,v)$ 减去増广的流量,将 $w(v,u)$ 和 $ans$ 加上相同的值。

小剪枝:如果遍历完所有的 $v$ 后 $ans < flow$,意味着已经从 $u$ 流出了所有可以増广的流量,即 $u$ 已经满流了,此时需要将 $dep_u$ 设为 $-1$,防止再次从这个点増广。

优化

$\text{Dinic}$ 算法还有一个优化,被称为当前弧优化,即每次 $\text{DFS}$ 増广时不是从 $u$ 出发的第 $1$ 个点开始,而是用一个 $cur$ 数组记录点 $u$ 増广到了哪条边,从这条边开始増广,以此来进一步加速。

复杂度

$\text{Dinic}$ 算法的时间复杂度为 $\mathcal O(n^2m)$。我们可以证明最多需要建立 $\mathcal O(n)$ 个层次图,每次建立层次图的复杂度为 $\mathcal O(m)$。接下来分析 $\text{DFS}$ 的复杂度,每次最多増广 $\mathcal O(m)$ 次,每次修改流量的复杂度为 $\mathcal O(n)$,所以 $\text{DFS}$ 的复杂度为 $\mathcal O(nm)$。再加上 $\mathcal O(n)$ 个层次图,总复杂度为 $\mathcal O(n^2m)$。绝大多数情况下这个复杂度都跑不满。

对于 $\text{Dinic}$ 算法的复杂度,有如下 $3$ 种情况:

  1. 一般的网络图:$\mathcal O(n^2m)$
  2. 单位容量的图:$\mathcal O(\min(\sqrt m,n^{\frac{2}{3}})\cdot m)$
  3. 二分图:$\mathcal O(m\sqrt n)$

代码

void addEdge(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w;
}
void addArc(int u, int v, int w) {
    addEdge(u, v, w), addEdge(v, u, 0);
}
bool bfs(int s, int t) {
    std::queue<int> q;
    std::fill(dis + s, dis + t + 1, -1);
    std::copy(lnk + s, lnk + t + 1, cur + s);
    dis[s] = 0, q.push(s);
    for (; !q.empty(); ) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] > flow[i] && dis[v] < 0) {
                dis[v] = dis[u] + 1, q.push(v);
            }
        }
    }
    return dis[t] >= 0;
}
int dfs(int u, int t, int f) {
    if (u == t) return f;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] > flow[i] && dis[v] == dis[u] + 1) {
            int x = dfs(v, t, std::min(f, cap[i] - flow[i]));
            flow[i] += x, flow[i ^ 1] -= x, f -= x, ans += x;
            if (f == 0) break;
        }
    }
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    for (; bfs(s, t); ) {
        for(int x; (x = dfs(s, t, INF)); ans += x);
    }
    return ans;
}

习题


网络流 24 题

发表评论