网络流算法笔记

洛谷全站推荐

定义

网络是一种特殊的有向图 $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$ 的残量网络。

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

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

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

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

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

首先我们还是正常增广：

然后我们又这样增广：

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

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

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

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

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

---

Edmond-Karp

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

思路

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

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

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

时间复杂度

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

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

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

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

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

还是太慢了。

---

Dinic

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

思路

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

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

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

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

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

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

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

其实有的时候题目的数据虽然很大，但是 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

这个算法是比 dinic 还要快的一种算法，但是网络流的数据一般不会卡 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$。

最后直接在建好的图上跑 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$

思路

第一个答案你肯定会，白痴 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定理

定理的具体内容就是：对于任意网络 $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$，每流一单位的流量就要付出代价。

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

概述

假如没有负环，解决方法很简单，我们连反向边的时候代价为$-c$就可以了，然后我们增广的时候需要找到$c$最短的路增广即可。

最坏复杂度能达到 $O \left ( nmf \right )$，这里 $f$ 是增广的次数。

有负环的情况估计就不算网络流基础了，可以自行了解。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct MinCostMaxFlow
{
    int n, m, s, t, cnt = 0, head[1111111], cur[1111111], dist[1111111], mincost;
    bool vis[1111111];
    struct edge {
        int v, nxt, cap, flow, cost;
    } edges[22222222];
    
    void init(int _n, int _s, int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        cnt = 0;
        memset(head, -1, sizeof(head));
    }
    
    void addedge(int u, int v, int w, int c) {
        edges[cnt] = {v, head[u], w, 0, c};
        head[u] = cnt++;
        edges[cnt] = {u, head[v], 0, 0, -c};
        head[v] = cnt++;
    }
    
    bool spfa(int s, int t)
    {
        for (int i = 0; i <= n; i++) {
            dist[i] = 0x3f3f3f3f3f;
        }
        memcpy(cur, head, sizeof(head));
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        vis[s] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop(), vis[u] = 0;
            for (int i = head[u]; ~i; i = edges[i].nxt)
            {
                if (edges[i].cap > edges[i].flow && dist[edges[i].v] > dist[u] + edges[i].cost)
                {
                    dist[edges[i].v] = dist[u] + edges[i].cost;
                    if (!vis[edges[i].v])
                        q.push(edges[i].v), vis[edges[i].v] = 1;
                }
            }
        }
        return dist[t] != 0x3f3f3f3f3f;
    }
    
    int dfs(int u, int t, int flow)
    {
        if (u == t) {
            return flow;
        }
        vis[u] = 1;
        int ans = 0;
        for (int &i = cur[u]; ~i && ans < flow; i = edges[i].nxt) {
            if (!vis[edges[i].v] && edges[i].cap > edges[i].flow && dist[edges[i].v] == dist[u] + edges[i].cost) {
                int f = dfs(edges[i].v, t, min(edges[i].cap - edges[i].flow, flow - ans));
                if (f) {
                    mincost += f * edges[i].cost;
                    edges[i].flow += f;
                    edges[i ^ 1].flow -= f;
                    ans += f;
                }
            }
        }
        vis[u] = 0;
        return ans;
    }
    
    int mcmf() {
        int ans = 0;
        while (spfa(s, t)) {
            int x;
            while ((x = dfs(s, t, 0x3f3f3f3f3f))){ 
                ans += x;
            }
        }
        return ans;
    }
}g;

最小费用循环流

老师只讲了个概念，但是我还是写。

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

例题

P3381 【模板】最小费用最大流

题目描述

给出一个包含 $n$ 个点和 $m$ 条边的有向图（下面称其为网络） $G=(V,E)$，该网络上所有点分别编号为 $1 \sim n$，所有边分别编号为 $1\sim m$，其中该网络的源点为 $s$，汇点为 $t$，网络上的每条边 $(u,v)$ 都有一个流量限制 $w(u,v)$ 和单位流量的费用 $c(u,v)$。

你需要给每条边 $(u,v)$ 确定一个流量 $f(u,v)$，要求：

1. $0 \leq f(u,v) \leq w(u,v)$（每条边的流量不超过其流量限制）；
2. $\forall p \in \{V \setminus \{s,t\}\}$，$\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)$（除了源点和汇点外，其他各点流入的流量和流出的流量相等）；
3. $\sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)$（源点流出的流量等于汇点流入的流量）。

定义网络 $G$ 的流量 $F(G)=\sum_{(s,i)\in E}f(s,i)$，网络 $G$ 的费用 $C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)$。

你需要求出该网络的最小费用最大流，即在 $F(G)$ 最大的前提下，使 $C(G)$ 最小。

对于 $100\%$ 的数据，$1 \leq n \leq 5\times 10^3$，$1 \leq m \leq 5 \times 10^4$，$1 \leq s,t \leq n$，$u_i \neq v_i$，$0 \leq w_i,c_i \leq 10^3$，且该网络的最大流和最小费用 $\leq 2^{31}-1$。

输入数据随机生成。

思路

发现数据范围小的吓人，那么直接上板子秒了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct MinCostMaxFlow
{
    int n, m, s, t, cnt = 0, head[1111111], cur[1111111], dist[1111111], mincost;
    bool vis[1111111];
    struct edge {
        int v, nxt, cap, flow, cost;
    } edges[22222222];
    void init(int _n, int _s, int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        cnt = 0;
        memset(head, -1, sizeof(head));
    }
    void addedge(int u, int v, int w, int c) {
        edges[cnt] = {v, head[u], w, 0, c};
        head[u] = cnt++;
        edges[cnt] = {u, head[v], 0, 0, -c};
        head[v] = cnt++;
    }
    bool spfa(int s, int t)
    {
        for (int i = 0; i <= n; i++) {
            dist[i] = 0x3f3f3f3f3f;
        }
        memcpy(cur, head, sizeof(head));
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        vis[s] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop(), vis[u] = 0;
            for (int i = head[u]; ~i; i = edges[i].nxt)
            {
                if (edges[i].cap > edges[i].flow && dist[edges[i].v] > dist[u] + edges[i].cost)
                {
                    dist[edges[i].v] = dist[u] + edges[i].cost;
                    if (!vis[edges[i].v])
                        q.push(edges[i].v), vis[edges[i].v] = 1;
                }
            }
        }
        return dist[t] != 0x3f3f3f3f3f;
    }
    
    int dfs(int u, int t, int flow)
    {
        if (u == t) {
            return flow;
        }
        vis[u] = 1;
        int ans = 0;
        for (int &i = cur[u]; ~i && ans < flow; i = edges[i].nxt) {
            if (!vis[edges[i].v] && edges[i].cap > edges[i].flow && dist[edges[i].v] == dist[u] + edges[i].cost) {
                int f = dfs(edges[i].v, t, min(edges[i].cap - edges[i].flow, flow - ans));
                if (f) {
                    mincost += f * edges[i].cost;
                    edges[i].flow += f;
                    edges[i ^ 1].flow -= f;
                    ans += f;
                }
            }
        }
        vis[u] = 0;
        return ans;
    }
    int mcmf() {
        int ans = 0;
        while (spfa(s, t)) {
            int x;
            while ((x = dfs(s, t, 0x3f3f3f3f3f))){ 
                ans += x;
            }
        }
        return ans;
    }
}g;
signed main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cout.tie(0);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    g.init(n, s, t);
    for (int i = 1; i <= m; i++) {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        g.addedge(u, v, w, c);
    }
    cout << g.mcmf() << ' ' << g.mincost;
    return 0;
}

P1251 餐巾计划问题

题目描述

一个餐厅在相继的 $N$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾（$i = 1, 2, \dots, N$）。餐厅可以购买新的餐巾，每块餐巾的费用为 $p$ 分；或者把旧餐巾送到快洗部，洗一块需 $m$ 天，其费用为 $f$ 分；或者送到慢洗部，洗一块需 $n$ 天（$n \gt m$），其费用为 $s$ 分（$s \lt f$）。

每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $N$ 天中餐巾使用计划，使总的花费最小。编程找出一个最佳餐巾使用计划。

对于 $100 \%$ 的数据，$1 \le N \le 2 \times 10^3$，$1 \le r_i \le 10^7$，$1 \le p, f, s \le 10^4$。

思路

理解了mcmf的定义这题就很简单，但我认为这道题在24题里算比较难的一类。

还是建立超级源汇点，对于每一天我们都维护两个点，分别是干净的餐巾和脏了的餐巾，然后干净的向汇点连容量为 $a_i$ 的边，源点向不干净的连容量为 $a_i$ 的边，费用都是 $0$。最后我们只需要存这四种边：

• 第 $i$ 天的脏布往 $i + m$ 的干净布连容量为 $\infty$，代价为 $f$ 的边。相当于快洗部。

• 第 $i$ 天的脏布往 $i + n$ 的干净布连容量为 $\infty$，代价为 $s$ 的边。相当于慢洗部。

• 超级源点往 $i$ 的干净布连容量为 $\infty$，代价为 $p$ 的边。

• 第 $i$ 天的脏布往 $i + 1$ 的脏布连容量为 $\infty$，代价为 $0$ 的边。

最后求mcmf即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct MinCostMaxFlow
{
    int n, m, s, t, cnt = 0, head[1111111], cur[1111111], dist[1111111], mincost;
    bool vis[1111111];
    struct edge {
        int v, nxt, cap, flow, cost;
    } edges[22222222];
    void init(int _n, int _s, int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        cnt = 0;
        memset(head, -1, sizeof(head));
    }
    void addedge(int u, int v, int w, int c) {
        edges[cnt] = {v, head[u], w, 0, c};
        head[u] = cnt++;
        edges[cnt] = {u, head[v], 0, 0, -c};
        head[v] = cnt++;
    }
    bool spfa(int s, int t)
    {
        for (int i = 0; i <= n; i++) {
            dist[i] = 0x3f3f3f3f3f;
        }
        memcpy(cur, head, sizeof(head));
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        vis[s] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop(), vis[u] = 0;
            for (int i = head[u]; ~i; i = edges[i].nxt)
            {
                if (edges[i].cap > edges[i].flow && dist[edges[i].v] > dist[u] + edges[i].cost)
                {
                    dist[edges[i].v] = dist[u] + edges[i].cost;
                    if (!vis[edges[i].v])
                        q.push(edges[i].v), vis[edges[i].v] = 1;
                }
            }
        }
        return dist[t] != 0x3f3f3f3f3f;
    }
    
    int dfs(int u, int t, int flow)
    {
        if (u == t) {
            return flow;
        }
        vis[u] = 1;
        int ans = 0;
        for (int &i = cur[u]; ~i && ans < flow; i = edges[i].nxt) {
            if (!vis[edges[i].v] && edges[i].cap > edges[i].flow && dist[edges[i].v] == dist[u] + edges[i].cost) {
                int f = dfs(edges[i].v, t, min(edges[i].cap - edges[i].flow, flow - ans));
                if (f) {
                    mincost += f * edges[i].cost;
                    edges[i].flow += f;
                    edges[i ^ 1].flow -= f;
                    ans += f;
                }
            }
        }
        vis[u] = 0;
        return ans;
    }
    int mcmf() {
        int ans = 0;
        while (spfa(s, t)) {
            int x;
            while ((x = dfs(s, t, 0x3f3f3f3f3f))){ 
                ans += x;
            }
        }
        return ans;
    }
}g;
signed main()
{
    int n, p, m1, c1, m2, c2;
    cin >> n;
    g.init(n * 2 + 5, 0, n * 2 + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        g.addedge(0, i, a[i], 0);
        g.addedge(i + n, n * 2 + 1, a[i], 0);
    }
    cin >> p >> m1 >> c1 >> m2 >> c2;
    for (int i = 1; i <= n; i++) {
        if (i + 1 <= n) {
            g.addedge(i, i + 1, 0x3f3f3f3f, 0);
        }
        if (i + m1 <= n) {
            g.addedge(i, i + n + m1, 0x3f3f3f3f, c1);
        }
        if (i + m2 <= n) {
            g.addedge(i, i + n + m2, 0x3f3f3f3f, c2);
        }
        g.addedge(0, i + n, 0x3f3f3f3f, p);
    }
    g.mcmf();
    cout << g.mincost;
    return 0;
}

---

参考资料：

• OiWiki-网络流
• 算法导论P415~P449