最大流学习笔记

基本概念

流网络

流网络 $G = (V, E)$（Flow Network） 是一个有向图，图中每条边 $(u, v) \in E$ 有一个非负的 容量值 $c (u, v) \geq 0$。而且，如果边集合 $E$ 包含一条边 $(u, v)$，则图中不存在反方向的边 $(v, u)$。为了方便起见，如果 $(u, v) \notin E$，则定义 $c(u, v) = 0$。

在流网络的所有节点中，有两个特殊的点：源点 $s$ 和汇点 $t$ $(s \ne t)$。

流

设 $f(u, v)$ 定义在二元组 $(u \in V, v \in V)$ 上的实数函数且满足

1. 容量限制（Capacity Constraints）：对于每条边，流经该边的流量不得超过该边的容量，即 $\forall u, v \in V, f(u, v) \leq c(u, v)$；
2. 流量守恒（Flow Conservation）：从源点流出的流量等于汇点流入的流量，即 $\forall x \in V - \{s, t\}, \sum_{(u, x) \in E} f(u, x) = \sum_{(x, v) \in E} f(x, v)$；

那么 $f$ 称为网络 $G$ 的流函数。

对于 $(u, v) \in E$，$f(u, v)$ 称为边的 流量，$c(u, v) - f(u, v)$ 称为边的 剩余容量（Residual Capacity），可以记作 $c_f(u, v)$。整个网络的流量为 $\sum_{(s, v) \in E} f(s, v)$，即从源点发出的所有流量之和。为了方便起见，如果 $(u, v) \notin E$，则定义 $f(u, v) = 0$。

一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述两个性质。

流函数的完整定义如下：

$$f(u, v) = \left\{ \begin{aligned} & f(u, v), & (u, v) \in E \\ & -f(v, u), & (v, u) \in E \\ & 0, & (u, v) \notin E, (v, u) \notin E \\ \end{aligned} \right.$$

残量网络

对于流函数 $f$，残量网络 $G_f$（Residual Network）是网络 $G$ 中所有节点和剩余容量大于 $0$ 的边构成的子图，即

$$G_f = (V_f = V, E_f = \left \{(u, v) \in E , c_f(u, v) > 0 \right\})$$

注意，剩余容量大于 $0$ 的边可能不在原图 $G$ 中（根据容量、剩余容量的定义以及流函数的斜对称性得到）。可以理解为，残量网络中包括了那些还剩了流量空间的边构成的图，也包括虚边（即反向边）。

增广路

在原图 $G$ 中若存在一条从源点到汇点的路径上所有边的剩余容量都大于 $0$，则这条路径被称为增广路（Augmenting Path）。

Edmonds-Karp 算法

Edmonds-Karp 算法的基本思路很简单：不断地使用 BFS 去寻找增广路，直到网络上不存在增广路为止。

在每轮寻找增广路的过程中，Edmonds-Karp 算法只考虑所有 $c_f(u, v) \geq 0$ 的边，用 BFS 找到任意一条从 $s$ 到 $t$ 的路径，同时计算出路径上各边的剩余容量的最小值 $\mathit{minf}$，则网络的流量就可以增加 $\mathit{minf}$。

需要注意的是，当一条边的流量 $f(u, v) > 0$ 时，根据斜对称性质，它的反向边流量 $f(v, u) < 0$，此时必定有 $f(v, u) < c(v, u)$。故 Edmonds-Karp 算法在 BFS 时除了原图的边集 $E$ 外，还应该考虑遍历 $E$ 中每条边的反向边。

在实现时，只需要维护残量网络即可。当一条边 $(u, v)$ 流过大小为 $e$ 的流时，令 $(u, v)$ 的剩余容量减小 $(e)$，$(v, u)$ 的剩余流量增大 $e$ 即可。

Edmonds-Karp 算法的时间复杂度为 $O(VE^2)$。然而在实际运用中远远达不到这个上界，效率较高，可以处理 $10^3 \sim 10^4$ 规模的网络。

来自 GitHub Copilot 的补全（未验证）：然而在实际应用中，这个算法的时间复杂度可以降低到 $O(VE)$，因为在每轮 BFS 时，只需要更新 $E$ 中的边的剩余容量，而不需要更新 $V$ 中的节点。

代码

#include <cstring>
#include <iostream>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1005,
          M = 10005;

int n, m, s, t, ans;

// Graph
int idx, head[N], ver[M << 1], edge[M << 1], next[M << 1];

void add(int u, int v, int w) {
    next[idx] = head[u];
    ver[idx] = v;
    edge[idx] = w;
    head[u] = idx++;
}

// Edmonds-Karp
int d[N], pre[N];
bool vis[N];

bool bfs() {
    memset(vis, 0x00, sizeof(vis));
    std::queue<int> q;
    q.push(s);
    vis[s] = true;
    d[s] = std::numeric_limits<int>::max();
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = next[i]) {
            if (edge[i]) {
                int y = ver[i];
                if (vis[y]) continue;
                d[y] = std::min(d[x], edge[i]);
                pre[y] = i;  // 记录前驱
                q.push(y);
                vis[y] = true;
                if (y == t) return true;
            }
        }
    }
    return false;
}

void update() {  // 更新增广路及其反向边的剩余容量
    int x = t;
    while (x != s) {
        int i = pre[x];
        edge[i] -= d[t];
        edge[i ^ 1] += d[t];
        x = ver[i ^ 1];
    }
    ans += d[t];
}

int main() {
    std::ios::sync_with_stdio(false);
    memset(head, 0xff, sizeof(head));
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    while (bfs()) update();
    cout << ans << endl;
    return 0;
}

Dinic 算法

Edmonds-Karp 算法每轮可能会遍历整个残量网络，但只找出一条增广路，还有进一步优化的空间。

Dinic 算法不断重复以下步骤，直到在残量网络中 $s$ 不能到达 $t$：

1. 在残量网络上 BFS 求出节点的层次，构造分层图。
2. 在分层图上 DFS 求出增广路，在回溯时实时更新剩余容量。另外，每个点可以流向多条出边，同时还加入了若干剪枝（参考程序注释）。

Dinic 算法的时间复杂度为 $O(V^2E)$。但在实际中远远达不到这个上界，一般能够处理 $10^4 \sim 10^5$ 规模的网络，特别地，在求解稠密图上的最大流问题是效率要比前文提到的 Edmonds-Karp 算法更高。

Dinic 算法中的两个优化：

1. 多路增广：每找到一条增广路时，若还有残余流量存在，那么可以再找出其他的增广路来利用这些残余流量。这样就可以在一次 DFS 中找出多条增广路，大大提高了算法的效率。
2. 当前弧优化：如果一条边已经被增广过，那么该边就没有可能被增广第二次。那么，当下一次进行增广的时候，就可以不必再走那些已经被增广过的边。

代码

#include <cstring>
#include <iostream>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 205,
          M = 5005;

int n, m, s, t, flow;
long long ans;

// Graph
int idx, head[N], edge[M << 1], ver[M << 1], next[M << 1];

void add(int u, int v, int w) {
    next[idx] = head[u];
    edge[idx] = w;
    ver[idx] = v;
    head[u] = idx++;
}

// Dinic
int d[N], cur[N];

bool bfs() {
    memset(d, 0x00, sizeof(d));
    std::queue<int> q;
    d[s] = 1;
    q.push(s);
    cur[s] = head[s];

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = next[i]) {
            int v = ver[i],
                w = edge[i];
            if (w && !d[v]) {
                d[v] = d[u] + 1;
                cur[v] = head[v];
                if (v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dinic(int u, int limit) {
    if (u == t) return limit;

    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = next[i]) {
        cur[u] = i;            // 当前弧优化

        int v = ver[i],
            w = edge[i];
        if (w && d[v] == d[u] + 1) {
            int k = dinic(v, std::min(edge[i], limit - flow));
            if (!k) d[v] = 0;  // 剪枝：去掉增广完毕的点
            edge[i] -= k;
            edge[i ^ 1] += k;
            flow += k;
        }
    }
    return flow;
}

int main() {
    std::ios::sync_with_stdio(false);
    memset(head, 0xff, sizeof(head));
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    while (bfs()) {
        while (flow = dinic(s, 0x3f3f3f3f)) ans += flow;
    }
    cout << ans << endl;
    return 0;
}

参考资料

1. 0x6A 网络流初步，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
2. 第 26 章 最大流，《算法导论》中译本（ISBN 978-7-111-40701-0，机械工业出版社），2013 年 1 月第三版。
3. 1.1.1 网络流的基本概念，AcWing 算法进阶课，闫学灿，2020 年 7 月 25 日。
4. 1.1.2 最大流，AcWing 算法进阶课，闫学灿，2020 年 7 月 31 日 ~ 2020 年 8 月 8 日。
5. 网络流简介，图论，OI Wiki，2021 年 7 月 11 日。