网络流算法笔记

太好了！我终于学会网络流了！

定义

网络是一种特殊的有向图$G=(V,E)$，和一般的图不同在于每一条边都有一个非负的容量$c(u,v) \geq 0$，并且在这个图中还有两个特殊的点：源点和汇点。

我们定义流是一个实值函数$f : V \times V \to \mathbb{R}$，满足下面的性质：

• 容量限制：对于所有的结点$u,v \in V$，满足$0 \leq f(u,v) \leq c(u,v)$。

• 流量守恒：对于所有的结点$u \in V - {s,t}$，满足$\displaystyle \sum_{v \in V} f(v,u) = \sum_{v \in V} f(u, v)$。

当$u$与$v$不连通时，这两个结点之间没有流，$f(u,v) = 0$。

我们称非负数值$f(u,v)$是结点$u$到结点$v$的流。

一个流$\left |f \right |$的定义如下：

• $\left | f \right | = \displaystyle \sum_{v, \in V} f\left (s, v \right ) - \sum_{v, \in V} f \left (v, s \right )$。

最大流

引入

这个图就是一个典型的网络，我在每条边上都给了一个数字，表示这条边的容量。

题目描述

我们给一个在实际生活中会遇到的问题（打破次元壁）：

璃月港的「群玉阁」需要从「孤云阁」的遗迹守卫（源点$s$）采集元素能量，通过地下矿道网络输送到「层岩巨渊」的巨型熔炉（汇点$t$），以维持整个璃月的元素屏障。由于矿道存在容量限制，你需要计算最大流量。

最大流

下面是一种可能的运送方案：

这里每条边上面的两个数字，第一个表示流量，第二个表示这条边的容量。

观察这张图，你会发现每个除源汇点外的结点，流入和流出的流量都一样，并且流入汇点t的流量已经达到了最大值$18$，这张图的最大流就是$18$。（纯靠瞪眼构造这张图还是需要一点脑力的）

给一个最大流的严格定义：

令$G=\left (V,E \right )$是一个有源汇点的网络，我们希望为每条边指定一个流量，使得这个网络的流$\left | f \right |$尽量大。

那很好，我们该怎么求解最大流呢？

---

Ford-Fulkerson增广

引入

最大流问题最无脑思想就是不断找增广路，看看能否更新当前最大流的答案。可以当作是一种贪心。

但这一定对吗？？？

看这个例子，假如我们这么增广了：

（这张图一些边我给的权值太大了，举反例真不容易）

然后我们又这么增广了：

你就会发现！现在绿色箭头走出来的大小为$4$的流量虽然可以通过容量为$14$的那条边流到$t$，但是现在完成之后简单思考可得出无法达到最大流$18$了！

怎么办呢？

概述

我们定义一条边$(u,v)$的容量与流量之差为剩余流量$c_f(u,v)$，这里$c_f(u,v)=c(u,v)-f(u,v)$。

我们把$G$中所有结点和所有剩余流量大于$0$的边合成出来的子图叫做$G$的残量网络。

我们前面提到的贪心策略的问题在于：它不能反悔。

要是我们增广出去的流量会使答案变小，我们就需要反悔操作来保证答案是正确的。

所以我们考虑在连每一条边的时候连上一条这个边的反向边，每次正边的剩余流量减少的时候，反向边的剩余流量就增多。

那我们在增广的时候，要是选择了一条反向边，就相当于完成了反悔的操作。

这么说你可能不太理解，我们还是拿图：

首先我们还是正常增广：

然后我们又这样增广：

这里第二条边用到了第一次增广后出来的反向边。

按照我们之前建立反向边的逻辑，这次增广又会把反向边流满，于是正向边又会出现，这就算是一次反悔的操作。于是我们惊奇的发现，前面两次增广造成的效果就等于：

所以我们中间的边就相当于没被影响！不难想到只要这样增广下去就一定能得到正确答案！

分析一下时间复杂度，因为我们每一次增广必然会增加答案，所以最坏的时间复杂度：$\mathrm{O}\left (\left | E \right | \times \left | f \right | \right )$。

虽然正确性有了，但太慢了。

---

Edmond-Karp

这个算法虽然还不是最快的，但是还是有必要看一看，为后面$\text{dinic}$做准备。

思路

首先我们在$G_f$中只要能从源点$s$ $\text{BFS}$到汇点$t$，这就表示我们一定能增广出去增加答案，对吧？

我们每次增广的时候，记录增广路所有经过的边的剩余容量的最小值$f$，并把每一条边的剩余容量减去$f$，同时也把这些边的反向边的剩余容量增加$f$。

那我们的$\text{BFS}$在什么时候结束呢？只要汇点$t$接收不到流的时候表示我们源点$s$已经和$t$不在同一个连通分量上了，所以就可以停下来了。

时间复杂度

时间复杂度为$\mathrm{O} \left (\left | V \right | \left | E \right |^2 \right )$。

由于篇幅所限，我们给的证明不一定足够详细和准确，对证明感兴趣的可以去OiWiki上寻找更详细的证明。

首先我们每次增广的时候，必然会增加答案，所以肯定会消失一条正向边，取而代之的是反向边。

因为我们采用的方法是$\text{BFS}$，所以从$s$到$t$的最短路肯定是非降的，所以增广总轮数的上界是$\mathrm{O} \left ( \left | V \right | \left | E \right | \right )$。

乘上单轮增广的时间复杂度就是$\mathrm{O} \left (\left | V \right | \left | E \right |^2 \right )$了。

还是太慢了。

---

Dinic

这个算法是在网络流中非常常用的算法，请务必掌握。

思路

考虑每次用$\text{BFS}$在$G_f$上算出$s$到所有结点的距离，然后建立新的分层图图$G_l$。

对于原图中的所有边，我们在$G_l$中只保留连接相邻两层的边，然后在这张图上$\text{DFS}$，找到一个极大的流$f_b$，使得在$G_l$上无法扩大$f_b$，就把$f_b$累加到答案$f$里。

然后一直重复上面这两步操作，直到$s$与$t$连接为止。此时的$f$就是最大流。

这里还要引入一个保证时间复杂度正确性的当前弧优化，对于一个结点$u$，要是我们知道$u$有一条边$\left ( u,v \right )$已经增广到了极限，我们就不用尝试再流过这条边。

所以对于每个结点，我们维护它的出边里第一条它还可以增广出去的边，这个第一条边就叫做当前弧。

时间复杂度$\mathrm{O} \left ( \left | V \right | ^2 \left | E \right | \right )$

严格的时间复杂度证明见OiWiki。

其实有的时候题目的数据虽然很大，但是$\text{dinic}$并不会跑满这个复杂度。

封装好的模板代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct flowGraph
{
    struct edge {
      int v, nxt, cap, flow;
    } edges[2222222];
    int head[2222222], cnt = 0;
    int n, S, T;
    int maxflow = 0;
    int dist[2222222], cur[2222222];
    void init(int _n, int _S, int _T) {
        memset(head, -1, sizeof(head));
        cnt = 0;
        S = _S;
        T = _T;
        n = _n;
    }
    void addedge(int u, int v, int w) {
        edges[cnt] = {v, head[u], w, 0};
        head[u] = cnt++;
        edges[cnt] = {u, head[v], 0, 0};
        head[v] = cnt++;
    }
    bool bfs() {
        queue<int> q;
        memset(dist, 0, sizeof(int) * (n + 1));
        dist[S] = 1;
        q.push(S);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edges[i].nxt) {
                int v = edges[i].v;
                if ((!dist[v]) && (edges[i].cap > edges[i].flow)) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        return dist[T];
    }
    int dfs(int u, int flow) {
        if ((u == T) || (!flow)) {
            return flow;
        }
        int res = 0;
        for (int &i = cur[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].v, f;
            if ((dist[v] == dist[u] + 1) && (f = dfs(v, min(flow - res, edges[i].cap - edges[i].flow)))) {
                res += f;
                edges[i].flow += f;
                edges[i ^ 1].flow -= f;
                if (res == flow) {
                    return res;
                }
            }
        }
        return res;
    }
    int dinic() {
        while (bfs()) {
            memcpy(cur, head, sizeof(int) * (n + 1));
            maxflow += dfs(S, 0x3f3f3f3f3f3f);
        }
        return maxflow;
    }
} g;

ISAP

这个算法是比$\text{dinic}$还要快的一种算法，但是网络流的数据一般不会卡$\text{dinic}$的复杂度。

篇幅所限，感兴趣的读者可以到OiWiki研究。

例题

最大流的例题非常多，难度几乎都是紫题。

但是你只需要把上面我们求解最大流的知识学会了，其实下面的题只需要熟悉了套路很快就能秒一道。

P3376 【模板】网络最大流

模板题，直接用我上面封装好的模板代码即可。

// 省略模板...


signed main()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    g.init(n, s, t);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.addedge(u, v, w);
    }
    cout << g.dinic();
    return 0;
}

---

P2763 试题库问题

题目描述

问题描述：

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

编程任务：

对于给定的组卷要求，计算满足要求的组卷方案。

$2\leq k \leq 20$，$k \leq n \leq 10^3$。

思路

可以自己思考怎么把这道题转化为最大流问题。

我们考虑建立超级源点$s$与超级汇点$t$。

然后把$s$与所有题目连接，因为每个题目只能选$1$次，所以容量为$1$。

然后对于每个题目，把它和它所对应的类型连接，因为每个题目只能选一次，容量还是$1$。

然后对于每个类型，把它和超级汇点$t$连接，由于我们需要$k_i$个这个类型的题目，所以容量是$k_i$。

最后直接在建好的图上跑$\text{dinic}$计算最大流，得到的答案就是我们最多能选的题数。

要是得到的最大流$ < m$，就表示没有答案。

要是正好等于$m$，我们只需要看题目和类型之间的边，要是题目$u$和类型$v$这条边$\left ( u, v \right )$这条边有流量，就表示题目$u$作为类型$v$被选择了，

可以自己再想一想，其实不难。

代码

signed main()
{
    int k, n;
    cin >> k >> n;
    g.init(k + n + 3, 0, k + n + 2);
    vector<int> cnt(k + 1);
    int m = 0;
    for (int i = 1; i <= k; i++) {
        cin >> cnt[i];
        g.addedge(n + i, k + n + 2, cnt[i]);
        m += cnt[i];
    }
    vector<vector<int>> edges;
    for (int i = 1; i <= n; i++) {
        g.addedge(0, i, 1);
        int p;
        cin >> p;
        while (p--) {
            int x;
            cin >> x;
            edges.push_back({i, x, g.cnt});
            g.addedge(i, n + x, 1);
        }
    }
    if (g.dinic() == m) {
        vector<vector<int>> ans(k + 1);
        for (int i = 0; i < edges.size(); i++) {
            if (g.e[edges[i][2]].flow == 1) {
                ans[edges[i][1]].push_back(edges[i][0]);
            }
        }
        for (int i = 1; i <= k; i++) {
            cout << i << ": ";
            for (int j = 0; j < ans[i].size(); j++) {
                cout << ans[i][j] << ' ';
            }
            cout << '\n';
        }
    } else {
        cout << "No Solution!";
    }
    return 0;
}

P2766 最长不下降子序列问题

题目描述

给定正整数序列 $x_1 \ldots, x_n$。

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

令 $a_1, a_2, \ldots, a_s$ 为构造 $S$ 时所使用的下标，$b_1, b_2, \ldots, b_s$ 为构造 $T$ 时所使用的下标。且 $\forall i \in [1,s-1]$，都有 $a_i \lt a_{i+1}$，$b_i \lt b_{i+1}$。则 $S$ 和 $T$ 不同，当且仅当 $\exists i \in [1,s]$，使得 $a_i \neq b_i$。

$1 \le n\le 500$

思路

第一个答案你肯定会，白痴$\text{DP}$即可，$dp_i$就表示以$i$位置为结尾的最长不下降子序列长度，设答案为$S$。

第二个怎么做呢？可以先自己思考一下。

首先我们怎么在图中表示一段子序列呢？考虑用走过的一条路径表示，也就是说对于图中的一条路径，我们走过的点就是子序列。

那怎么连边呢？

我们还是建立超级源点$s$和$t$，我们对于每个数组中的位置$i$，要是这个点的$dp$值是$1$，就表示它肯定是一个子序列的开头才会对答案有贡献，所以我们把源点$s$和这个$i$连边，容量为$1$。

同理要是这个点的$dp$值是$S$，我们就把它和汇点$t$连边，容量为$1$。

然后我们检查每一对数组中的$(i,j)$，满足$i < j$。要是$a_i < a_j$，那$i$就能向$j$这个点贡献答案，所以连一条从$i$到$j$的边，容量为$1$。

但是这样做还是有一个问题，因为题目不允许选重复的位置，所以一个点对答案的贡献最多为$1$，所以通过这个点的流量也最多为$1$。这个时候该怎么办呢？我们考虑把点拆开，把拆出来的这两个点之间连接一条容量为$1$的边，这样就能把通过这个点的容量卡到$1$以下。

这个时候跑最大流就可以得到第二个答案了。请想清楚原理。

那第三个答案允许第一个和最后一个元素重复选，我们直接把拆这两个点连的边之间的流量改为无穷大即可。

代码

signed main()
{
    int n;
    cin >> n;
    if (n == 1) { // 注意特判！
        cout << 1 << '\n';
        cout << 1 << '\n';
        cout << 1 << '\n';
        return 0;
    }
    vector<int> a(n + 1), dp(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int s = -1;
    for (int i = 1; i <= n; i++) {
        s = max(s, dp[i]);
    }
    cout << s << '\n';
    g.init(n + n + 2, 0, n + n + 1);
    for (int i = 1; i <= n; i++) {
        g.addedge(i, i + n, 1);
    }
    for (int i = 1; i <= n; i++) {
        if (dp[i] == 1) {
            g.addedge(0, i, 1);
        }
        if (dp[i] == s) {
            g.addedge(i + n, n + n + 1, 1);
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i] && dp[j] + 1 == dp[i]) {
                g.addedge(j + n, i, 1);
            }
        }
    }
    int tp = g.dinic();
    cout << tp << '\n';
    g.addedge(0, 1, INT_MAX);
    g.addedge(1, 1 + n, INT_MAX);
    if (dp[n] == s) {
        g.addedge(n, n + n, INT_MAX);
        g.addedge(n + n, n + n + 1, INT_MAX);
    }
    cout << tp + g.dinic() << '\n';
    return 0;
}

---

最小割

引入

对于一个网络，我们定义它的割为一种点的划分方式：

把所有的点划分为两个集合$S$和$T$，这里源点$s \in S$，汇点$t \in T$。

割的容量就是所以从$S$连向$T$的边的容量之和。

最小割就是要求出最小的割的容量。

Kőnig定理

不是$\text{cod}$里的那个$\text{Konig}$！

定理的具体内容就是：对于任意网络$G = \left ( V , E \right)$，图中的最大流就等于最小割。

篇幅所限，感兴趣读者可以到OiWiki寻求严谨的证明。

例题

大量水紫题来袭！

P2762 太空飞行计划问题

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $ E = { E_1, E_2, \cdots, E_m } $，和进行这些实验需要使用的全部仪器的集合 $ I = { I_1, I_2, \cdots, I_n } $。实验 $ E_j $ 需要用到的仪器是 $ I $ 的子集 $ R_j \subseteq I $。

配置仪器 $ I_k $ 的费用为 $ c_k $ 美元。实验 $ E_j $ 的赞助商已同意为该实验结果支付 $ p_j $ 美元。W 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

$1 \leq n, m \leq 50 ，1 \leq c,p < 2^{31} $。

思路

可以先自行思考这个问题，要是从最大流的角度去想不太好解决。

考虑用最小割解决这个问题，根据最小割的定义，我们会把所有的点划分为两个集合。这个问题里每个结点是选还是不选其实也是对应了两种状态，所以可以考虑用划分的集合表示哪些仪器选了，哪些没选。

具体怎么做？我们先把超级源点$s$往所有实验连边，容量为$b_i$。然后把所有实验往汇点连边，容量为$c_i$。

然后我们再把所有实验和对应的仪器连边，这里的容量就要设置成$\infty$。

为什么要这么做呢？因为我们要是直接在这张图上跑最小割，那一定不会割掉实验和仪器之间的边，这就表示我们实验和仪器肯定不会再不同的集合中，也就表示我们的实验要是选了，仪器肯定都选了。

那我们跑完最小割得到的答案表示什么呢？就表示我们舍弃了哪些$b_i$和选择了哪些$c_i$，因为保证了源点和汇点不在同一个集合。

所以我们最终的答案就是$b$中的元素之和减去图上的最小割。这是最小割最典型的一道例题，请务必理解上面的思路。

读入还是需要一点手法的。

代码

signed main()
{
    int m, n;
    cin >> m >> n;
    g.init(n + m + 5, 0, n + m + 1);
    vector<vector<int>> a(m + 1);
    vector<int> b(m + 1);
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        cnt += b[i];
        g.addedge(0, i, b[i]);
        while (getchar() == ' ') {
            int x;
            cin >> x;
            g.addedge(i, x + m, 0x3f3f3f3f);
        }
    }
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        g.addedge(i + m, n + m + 1, c[i]);
    }
    int tp = g.dinic();
    for (int i = 1; i <= m; i++) {
        if (g.dist[i]) {
            cout << i << ' ';
        }
    }
    cout << '\n';
    for (int i = 1; i <= n; i++) {
        if (g.dist[i + m]) {
            cout << i << ' ';
        }
    }
    cout << '\n';
    cout << cnt - tp;
    return 0;
}

P4177 [CEOI 2008] order

题目描述

有 $N$ 个工作，$M$ 种机器，每种机器可以租或者买。每个工作包括若干道工序，每道工序需要某种机器来完成。

你需要最大化利益。

对于 $100\%$ 的数据满足 $1\le N,M\le 1200，1\le x_i\le 5000，b_{ij},y_i\le 20000$。

思路

这道题与上一道题唯一的区别在于可以租机器。我们建图还是一模一样，但是对于工作和机器之间的连边直接连租的费用即可。

代码

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    g.init(n + m + 111, 0, n + m + 10);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        cnt += x;
        g.addedge(0, i, x);
        while (y--) {
            int tp1, tp2;
            cin >> tp1 >> tp2;
            g.addedge(i, tp1 + n, tp2);
        }
    }
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        g.addedge(i + n, n + m + 10, x);
    }
    cout << cnt - g.dinic();
    return 0;
}

---

费用流

引入

假如我们每条边上有一个费用单位$c$，然后每流$1$个单位的流量就要付出$c$的代价。现在让你在最大流的同时要最小化代价，你怎么做？？？？

最小费用最大流

定义

我们给每条边指定一个费用$c$，每流一单位的流量就要付出代价。

最小费用最大流就是要保证在最大流基础上，让代价最小。

概述

最小费用循环流

网络流高阶内容。只知道定义即可：

没有源汇点，要求每个点流量平衡（流入$=$流出）

---

参考资料：

• OiWiki-网络流