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

网络流系列文章

  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 题

最后修改：2019 年 09 月 25 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏