网络流——图论的“终极”算法¶

第一部分：最大流

计算机学院 21 级何丰辰

视频讲解

最大流入门

1. 前置知识¶

图的存储
图的遍历
最短路
二分图

2. 基础定义¶

网络/流网络 指一个有向图，其每条边都有一个权值，称之为容量。其中有两个特殊点：源点 $s$ 和汇点 $t$ 。
容量限制 对于网络中的每条边，流经该边的流量不能超过该边的容量
斜对称性 每条边的流量与其相反边的流量之和为 0（其相反边可以是虚拟的边）
流守恒性 源点流出的流量等于汇点流入的流量
剩余容量 容量-流量
网络的流量 源点流出的所有流量之和

3. 最大流的三种算法¶

3.1 定义¶

最大流 网络的流量最大
阻塞流 无法再从源点向汇点输出流量
残量网络 原网络中所有结点和 剩余容量大于 0 的边（包括了反向边）构成的子图
增广路 残量网络中从源点到汇点的路径

3.2 朴素算法¶

3.2.1 算法描述¶

寻找任意一条从源点到汇点的简单路径（即不存在回路的路径），若找到则进行步骤 2，若找不到则跳到步骤 5
定义瓶颈容量为路径上所有的边的容量的最小值
将路径上所有的边的容量减去瓶颈容量，更新残量网络
跳到步骤 1
最大流=源点的出边的容量-剩余容量=汇点的入边的容量-剩余容量

3.2.2 算法缺陷¶

只能找到阻塞流，不能保证找到最大流！

3.3 Ford-Fulkerson 算法¶

3.3.1 算法描述¶

寻找任意一条从源点到汇点的简单路径（即不存在回路的路径），若找到则进行步骤 2，若找不到则跳到步骤 6
定义瓶颈容量为路径上所有的边的容量的最小值
将路径上所有的边的容量减去瓶颈容量，更新残量网络
跳到步骤 1
添加一条反向路径
最大流=源点的出边的容量-剩余容量=汇点的入边的容量-剩余容量

3.3.2 算法缺陷¶

时间复杂度受边权影响！

最坏的时间复杂度为 $O(mf)$ ， $m$ 为边数， $f$ 为最大流的流量

3.4 Edmonds-Karp 算法¶

3.4.1 算法描述¶

寻找任意一条从源点到汇点的最短路径（找最短路时 不考虑边权，即边权全部为 1），若找到则进行步骤 2，若找不到则跳到步骤 6
定义瓶颈容量为路径上所有的边的容量的最小值
将路径上所有的边的容量减去瓶颈容量，更新残量网络
跳到步骤 1
添加一条反向路径
最大流=源点的出边的容量-剩余容量=汇点的入边的容量-剩余容量

3.4.2 算法时间复杂度分析¶

边数最多为 $2m$ （加上反向边）因此每一轮循环中，寻找最短路需要 $O(m)$ 最多进行 $mn$ 轮循环（证明过程较为繁琐，不展开叙述）因此最坏总时间复杂度为 $O(m^2n)$ ，其中 $m$ 为边数， $n$ 为结点数实际使用中往往达不到最坏情况，能够处理 $10^3-10^4$ 规模的网络

3.5 Dinic 算法¶

3.5.1 算法描述¶

BFS 将图分层构建 分层网络，若源点无法到达汇点则跳到步骤 5
在分层网络中 DFS 寻找阻塞流并更新残差网络
在残差网络中添加反向边
跳到步骤 1
最大流=源点的出边的容量-剩余容量=汇点的入边的容量-剩余容量

3.5.2 算法时间复杂度分析¶

每一轮循环中，构建分层网络并寻找阻塞流最坏需要 $O(mn)$ 最多进行 $n-1$ 轮循环因此最坏时间复杂度为 $O(mn^2)$ ，其中 $m$ 为边数， $n$ 为结点数实际使用中往往达不到最坏情况，能够处理 $10^4-10^5$ 规模的网络 Dinic 是求解网络最大流问题中最常使用的算法

3.5.3 算法模板¶

namespace Dinic {
    const int N = 1e5 + 7, M = 2e6 + 7;
    const ll inf = 1e18;
    int n, S, T, d[N];
    int h[N], hi[N], e[M], t[M], tot;
    ll f[M], mxf;

    inline void add(int x, int y, ll z, bool o = 1) {
        e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0, 0);
    }

    inline bool bfs() {
        for (int i = 1; i <= n; i++) d[i] = 0;
        queue<int> q;
        q.push(S), d[S] = 1;
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int i = h[x]; i; i = t[i]) {
                int y = e[i];
                ll z = f[i];
                if (d[y] || !z) continue;
                q.push(y), d[y] = d[x] + 1;
                if (y == T) return 1;
            }
        }
        return 0;
    }

    ll dfs(int x, ll now = inf) {
        if (x == T) return now;
        ll rst = now;
        for (int &i = hi[x]; i; i = t[i]) {
            int y = e[i];
            ll z = f[i];
            if (d[y] != d[x] + 1 || !z) continue;
            ll k = dfs(y, min(z, rst));
            if (!k) d[y] = 0;
            else f[i] -= k, f[i^1] += k, rst -= k;
            if (!rst) break;
        }
        return now - rst;
    }

    inline void main() {
        while (bfs()) {
            for (int i = 1; i <= n; i++) hi[i] = h[i];
            ll now;
            while ((now = dfs(S))) mxf += now;
        }
    }

    inline void init(int _n, int _S, int _T) {
        n = _n, S = _S, T = _T, tot = 1, mxf = 0;
        for (int i = 1; i <= n; i++) h[i] = 0;
    }
}

3.6 最大流三种算法对比¶

	时间复杂度	能够处理的数据规模
Ford-Fulkerson	$O(mf)$	与网络的最大流量相关
Edmonds-Karp	$O(nm^2)$	$10^3-10^4$
Dinic	$O(n^2m)$	$10^4-10^5$

4. 最大流的应用¶

4.1 二分图匹配¶

二分图匹配：给定一个二分图 𝐺，在 𝐺 的一个子图 𝑀 中，𝑀 的边集{𝐸}中的任意两条边都不相交，则称 𝑀 是一个匹配

4.1.1 二分图最大匹配¶

二分图最大匹配即使边数最多的匹配

一般的算法是匈牙利算法，但可以通过将源点连向左部点，将右部点连向汇点，容量均为 1，这样这个网络的最大流就等于原始二分图的最大匹配数

例题

飞行员配对方案问题

题目背景

第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

题目描述

一共有 $n$ 个飞行员，其中有 $m$ 个外籍飞行员和 $(n - m)$ 个英国飞行员，外籍飞行员从 $1$ 到 $m$ 编号，英国飞行员从 $m + 1$ 到 $n$ 编号。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。保证 $1 \leq m \leq n < 100$ ， $1 \leq u \leq m < v \leq n$ ，同一组配对关系只会给出一次。

解题思路

英国飞行员视为左部节点，外国飞行员视为右部节点，所有边的容量均为 1，直接跑二分图最大匹配即可

时间复杂度对比

二分图最大匹配	时间复杂度
匈牙利算法	$O(nm)$
Dinic	$O(\sqrt{n}m)$

可以发现 Dinic 算法在求解二分图最大匹配时比匈牙利算法更加高效（具体证明略）

4.1.2 二分图多重匹配¶

二分图多重匹配即每个节点不一定只与一条边相连，而是限制了最多连的边数（当限制为 1 时退化为二分图最大匹配）

普通的匈牙利算法难以解决二分图多重匹配问题

与二分图最大匹配类似，只需将源点指向左部点，右部点指向汇点的容量变成结点允许连的最大边数即可

例题

圆桌问题

题目描述

有来自 $m$ 个不同单位的代表参加一次国际会议。第 $i$ 个单位派出了 $r_i$ 个代表。会议的餐厅共有 $n$ 张餐桌，第 $i$ 张餐桌可容纳 $c_i$ 个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。保证 $1 \leq m \leq 150$ ， $1 \leq n \leq 270$ ， $1 \leq r_i, c_i \leq 10^3$ 。

解题思路

单位是左部，桌子是右部，源点向单位连容量为单位数量的边，桌子向汇点连容量为桌子数量的边，单位和桌子内部连容量为 1 的边，然后跑最大流即可

例题

试题库问题

题目描述

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。保证 $2\leq k \leq 20$ ， $k \leq n \leq 10^3$ 。

解题思路

试题是左部，类型是右部，源点向左部连容量为 1 的边，右部向汇点连容量为右部点权重的边，左部和右部的内部连容量为 1 的边，然后跑最大流即可

4.2 最小路径覆盖¶

最小路径覆盖：在一个有向无环图中，找出最少的路径，使得这些路径经过了所有的点

4.2.1 最小不相交路径覆盖¶

最小不相交路径覆盖：路径不能相交如何将最小不相交路径覆盖问题转化为网络最大流问题？

例题

最小路径覆盖问题

题目描述

给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个定点恰好在 $P$ 的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个定点开始，长度也是任意的，特别地，可以为 $0$ 。 $G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。设计一个有效算法求一个 DAG（有向无环图） $G$ 的最小路径覆盖。保证 $1\leq n\leq 150$ ， $1\leq m\leq 6000$ 。

解题思路

把原图的每个点 $u$ 拆成两个点 $u_1$ 和 $u_2$ ，如果有一条有向边 $(a,b)$ ，则连边 $(a_2,b_1)$ ，容易发现这是一个二分图，那么使用 最小路径覆盖=原图节点数-新图最大匹配数 这一定理即可求出答案

定理证明

初始时每个点都是一条路径，每次找一条匹配边，代表合并两条路径由于路径不相交（即每个点的入度和出度至少有一个为 1），所以二分图上的边也不相交（如果相交则说明某个点的入度或出度大于 1），这正好是匹配的定义每条匹配边代表答案-1，所以最小路径覆盖=原图节点数-新图最大匹配数

4.2.2 最小可相交路径覆盖¶

最小可相交路径覆盖：路径可以相交

一般来说，对原图传递闭包，即若原图中 $(u,v)$ 连通，则增加边 $(u,v)$ 。这可以用 Floyd 算法 $O(n^3)$ 实现。然后对新图做最小不相交路径覆盖即可。因为在原图中相交的路径在传递闭包后可以拆分成另一条边，这样就不相交了。

例题

魔术球问题

题目描述

假设有 $n\ (1 \leq n \leq 55)$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1$ ， $2$ ， $3$ ，…的球

每次只能在某根柱子的最上面放球。

同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球

解题思路

把一个球 $x$ 拆成 $x_1$ 和 $x_2$ 源点连 $x_1$ ， $x_2$ 连汇点，容量均为 1 找到能与 $x$ 组成完全平方数的 $y$ ，将 $y$ 连向 $x_1$ 跑最大流

4.3 最多不相交路径¶

最多不相交路径：已知一些路径，每个节点只能属于一条路径，求能选择多少条路径使它们不相交

如何将最多不相交路径问题转化为网络最大流问题？

通用方法：拆点，将一个点拆成两个，然后连边，容量表示该点最多经过次数

例题

最长不下降子序列问题

题目描述

给定正整数序列 $x_1 \ldots, x_n。(1 \le n\le 500)$

计算其最长不下降子序列的长度 $s$ 。

如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。

如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ （其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个**不同的**长度为 $s$ 的不下降子序列。

解题思路

第一问：计算其最长不下降子序列的长度 $s$

DP 求 LIS：

$dp[i]$ 表示以 $a[i]$ 结尾的 LIS 长度初始 $dp[i]=1$ >>> $dp[i]=dp[j]+1(j<i,a[j]\leq a[i])$

第二问：如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列

若 $a[j]$ 加上 $a[i]$ 可以构成一个不下降子序列，则 $j<i,a[j]\leq a[i]$ 每个元素只能在一个序列中故按如下方式进行建图：

源点 $S=0,T=2n+1$ 将每个点拆成两个点， $i$ 向 $i+n$ 连边，容量为 1 如果 $dp[i]=1$ ，则 $s$ 向 $i$ 连边，容量为 1，这些元素即为子序列的头如果 $j<i$ ， $a[j]\leq a[i]$ ，则 $j+n$ 向 $i$ 连边，容量为 1 如果 $dp[i]=k$ （LIS 长度），则 $i+n$ 向 $t$ 连边，容量为 1，即为子序列的尾

第三问：如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ （其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个**不同的**长度为 $s$ 的不下降子序列

去除 $x_1$ 和 $x_n$ 的限制即可，可以加入边 $(S,1),(1,1+n),(n,2n),(2n,T)$ 且容量为 $inf$ 需要注意的是，当序列严格递减时， $dp[i]=1,s=1$ ，不存在 $i,j$ 满足 $j<i,a[j]\leq a[i]$ ，此时答案即为第二问答案

5. 拓展方向¶

5.1 “算法”之内¶

最大流还有更加快速的 预流推进算法，但一般情况下 Dinic 就足够解决最大流问题了
整个图论的难点往往不在于各种算法，而在于建图的过程，对于网络流问题也是如此，因此学习网络流需要进行大量刷题
网络流 24 题

5.2 “算法”之外¶

avatar

全文结束，谢谢阅读！

最后更新: 2022-12-30 09:03:45

网络流——图论的“终极”算法¶

1. 前置知识¶

2. 基础定义¶

3. 最大流的三种算法¶

3.1 定义¶

3.2 朴素算法¶

3.2.1 算法描述¶

3.2.2 算法缺陷¶

3.3 Ford-Fulkerson 算法¶

3.3.1 算法描述¶

3.3.2 算法缺陷¶

3.4 Edmonds-Karp 算法¶

3.4.1 算法描述¶

3.4.2 算法时间复杂度分析¶

3.5 Dinic 算法¶

3.5.1 算法描述¶

3.5.2 算法时间复杂度分析¶

3.5.3 算法模板¶

3.6 最大流三种算法对比¶

4. 最大流的应用¶

4.1 二分图匹配¶

4.1.1 二分图最大匹配¶

4.1.2 二分图多重匹配¶

4.2 最小路径覆盖¶

4.2.1 最小不相交路径覆盖¶

4.2.2 最小可相交路径覆盖¶

4.3 最多不相交路径¶

5. 拓展方向¶

5.1 “算法”之内¶

5.2 “算法”之外¶

评论