简析网络流

DanielDingDang · 2025-05-22 11:20:25 · 个人记录

简析网络流

引言

在万物互联的数字时代，无数信息流在光纤中奔涌，物流网络支撑着全球贸易的血脉，电力网络点亮现代文明的星空。这些看似迥异的系统背后，隐藏着一种精妙的数学模型——网络流。这个诞生于二十世纪中期的图论分支，早已超越数学的藩篱，成为解码复杂系统运行规律的金钥匙。从福特-富尔克森算法掀起的第一次算法革命，到如今支撑着云计算资源调度的智能决策，网络流理论不断突破时空界限，在数字世界的每个节点上演绎着最优化的奇迹。

本文中，笔者将会简述网络流及其应用，希望能给您带来一些帮助！

最大流

概念简析

我们先作如下概念和规定。

网络是指一个有向图 G=(V,E)。和普通的有向图不同的是，他的每条边的权值被我们成为容量，例如 u 到 v 的边的容量，即这条边的权值，我们可以记作 c(u, v)。当然，如果 u 到 v 中间没有边，即 (u,v)\notin E 时，我们假设 c(u, v) = 0。如果我们把每条边想象成一个管道，那么 c(u, v) 可以理解成管道内可以通过的最大水量。而且，这个图也有一个源点 S 和一个汇点 T。你可以理解成，在这个管道组成的图中，我们希望把水从 S 点流向 T 点。

接下来，网络 G=(V,E)，我们定义流。流，形式化来说是个从边集 E 到整数集或实数集的函数，但我们本质上是在每条边上写上一个数 f(u, v)，可以理解成管道中流过了多少水，这也被称为边 (u, v) 的流量。但是这些数需要满足以下两个条件，才能被称作一个流：

容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 0 \leq f(u,v) \leq c(u,v)。这个可以理解为：管道中流过的水量不能超过管道的容量。
流量守恒：除源汇点外，任意结点 u 的净流量为 0。其中，我们定义 u 的净流量为 f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u)。这个可以理解为：对于每一个连接管道的节点，流入该点的总水量等于流出该点的总水量。

显然，源节点发出的流量总和等于汇节点接受的流量总和。

上述概念不需要记住具体准确的定义，只需要大致了解含义即可。

算法简注

终于，我们可以定义最大流的问题了。令 G=(V,E) 是一个有源汇点的网络，我们希望在 G 上指定合适的流 f，以最大化整个网络的流量 |f|，这个结果被称为原图的最大流。相当于是，水源在点 S，请找出一个流，使得净通过 T 的水量最大，求出这个值。

我们来通过一个例子感受下：（以下所有图都用邻接矩阵的方式呈现，同学们可以自己画在纸上理解一下，空的格子表示没有边）

	T	1	2
S	20		30
T
1	30
2	20	30

存在 3 条路径：

故流量总计 20+20+10=50。这就是最大流。

那我们如何解决这个问题？接下来介绍的思想叫做 Ford-Fulkerson 思想。

注意到，在寻找增广路的时候，在前面找到的不一定是一个最优解，如果我们建一个流量相反的边，那么就代表可以从这条反向边流过而实现反悔。

我们对于原图中的每一条边 u\rightarrow v，我们都建立一条反向边 v\rightarrow u，一开始边权为 0。

还是以刚才的图为例（整个解析过程中都是如此），建立这样的反向边。

	S	T	1	2
S		20		30
T	0		0	0
1		30		0
2	0	20	30

接下来，我们每次从源点 S 到 T 找路径 p，称这个路径是一条增广路。我们设该路径的长度为 l_p，路径上的边分别为 (u_1,v_1,w_1),(u_2,v_2,w_2),\cdots,(u_{l_p},v_{l_p},w_{l_p})。找到的路径要满足，\forall 1\le i\le p, w_i>0。也就是说，每条边的权值都得 >0。

找到一条这样的路径之后，我们令 \Delta=\min(w_i)。然后我们进行如下操作：顺次枚举路径上的每一条边，给 p 上的每条边都加上 \Delta 流量，并给它们的反向边都退掉 \Delta 流量，令最大流增加了 \Delta。换句话说，我们给路径上的每一条边 (u_i, v_i) 的权值都 -\Delta，给每一条反向边 (v_i, u_i) 的权值都 +\Delta，同时答案加上 \Delta。

我们不断寻找增广路，并进行上述过程，就可以得到一个可以证明正确性的网络流算法。

接下来，我们用上面的例子演示这个过程。一开始，我们的邻接矩阵如下：

	S	T	1	2
S		20		30
T	0		0	0
1		30		0
2	0	20	30

我们先找到一条路径 S\rightarrow T，那么这条路径上只有一条边 (S,T,20)。所以这条边的权值 -20，反向边 T\rightarrow S 的权值 +20，答案变成 20。这个时候邻接矩阵如下：

	S	T	1	2
S		0		30
T	20		0	0
1		30		0
2	0	20	30

接下来找到一条路径 S\to 2\to T。这个时候我们的路径中有 (S,2,30),(2,T,20) 这两条边。此时 \Delta=\min(20,30)=20，原边 (S,2,30),(2,T,20) 的边权 -\Delta，变成了 (S,2,10),(2,T,0)；而反向边 (2,S,0),(T,2,0) 的边权 +\Delta，变成了 (2,S,20),(T,2,20)；答案 +\Delta，此时答案为 20+20=40。这个时候邻接矩阵如下：

	S	T	1	2
S		0		10
T	20		0	20
1		30		0
2	20	0	30

这个时候，满足条件的增广路只有一条了，S\rightarrow 2\rightarrow 1\rightarrow T，只有他满足每条边的权值都大于 0，那我们可以有 (S,2,10),(2,1,30),(1,T,30) 这三条边。我们的 \Delta=\min(10,30,30)=10。原边 (S,2,10),(2,1,30),(1,T,30) 的边权分别 -\Delta，得到了 (S,2,0),(2,1,20),(1,T,20)；反向边 (2,S,20),(1,2,0),(T,1,0) 得到边权分别 +\Delta，得到了 (2,S,30),(1,2,10),(T,1,10)。答案变成 40+10=50。这个时候邻接矩阵如下：

	S	T	1	2
S		0		0
T	20		10	20
1		20		10
2	30	0	20

容易发现，从 S 出发的边的边权都是 0，所以肯定不存在一条合法的增广路了，FF 算法终止，得到答案为 50，符合预期。

当我们考虑 FF 增广的具体实现时，最自然的方案就是使用 BFS。此时，FF 增广表现为 Edmonds-Karp 算法。换句话说，我们用 BFS，每次找一条增广路就可以了。

那么这个算法的复杂度是多少呢？显然，单轮 BFS 增广的时间复杂度是 O(|E|)。可以证明，增广总轮数的上界是 O(|V||E|)。下面给出这个算法的代码实现。

bool bfs()
{
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    q[0] = S, st[S] = true, d[S] = INF;
    while (hh <= tt)
    {
        int u = q[hh ++ ];
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && f[i])
            {
                st[j] = true;
                d[j] = min(d[u], f[i]);
                pre[j] = i;
                if (j == T) return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int EK()
{
    int r = 0;
    while (bfs())
    {
        r += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
    }
    return r;
}

不难发现，整个过程中，复杂度完全取决于我们寻找增广路的效率。接下来，我们逐步优化算法，争取能一次找到多条增广路。我们令，原图加上权值为 0 的反向边的这张初始图为 G_f。

考虑在增广前先对 G_f 做 BFS 分层，即根据结点 u 到源点 S 的距离 d(u) 把结点分成若干层。令经过 u 的流量只能流向下一层的结点 v，即删除 u 向层数标号相等或更小的结点的出边，我们称 G_f 剩下的部分为分层图 G_L。形式化地，我们称 G_L = (V, E_L) 是 G_f = (V, E_f) 的分层图，其中 E_L = \left\{ (u, v) \mid (u, v) \in E_f, d(u) + 1 = d(v) \right\}。

分层图建出来之后，有了每个点的层数编号，对任意点 u 到点 v 的路径如果有 d(v)=d(u)+1，我们就可以判断该路径在一条最短增广路上。然后，我们使用 DFS 寻找增广路径。因为我们每次都是一层一层往下转移，每次选取的都是最短路径，所以用 O(|V|) 的复杂度 DFS 一次就找出许多条合法的增广路径。

这里有一个实用的技巧：多路增广。具体来说，如果我们在层次图上找到了一条从 S 到 T 的增广路 p，则接下来我们未必需要重新从 S 出发找下一条增广路，而可能从 p 上最后一个仍有剩余容量的位置出发寻找一条岔路进行增广。考虑到其与回溯形式的一致性，这一优化在 DFS 的代码实现中也是自然的。

但是直接这么做复杂度还是有点问题，这个时候我们考虑引入当前弧优化。

注意到在 G_L 上述 DFS 的过程中，如果结点 u 同时具有大量入边和出边，并且 u 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则 u 这个局部的时间复杂度最坏可达 O(|E|^2)。为避免这一缺陷，如果某一时刻我们已经知道边 (u, v) 已经增广到极限，则 u 的流量没有必要再尝试流向出边 (u, v)。据此，对于每个结点 u，我们维护 u 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。

这样以来，我们 Dinic 算法的时间复杂度为 O(n^2m)。

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T)  return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;  // 当前弧优化
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

算法应用

匹配问题

使用最大流算法，我们可以求出一个二分图的最大匹配。

给定一个二分图，其左部点的个数为 n，右部点的个数为 m，边数为 e，求其最大匹配的边数。

左部点从 1 至 n 编号，右部点从 1 至 m 编号。

我们可以先给出一个源点 S 和一个汇点 T。这个时候，我们把 S 向所有的左部点连边，把原图中有的左部点和右部点之间的边直接在网络中连起来，再把所有的右部点向汇点 T 连边。其中，以上提到的所有的边的容量都是 1。这个时候我们可以证明：二分图的最大匹配的大小就等于这个网络的最大流。

这一点如何证明呢？我们只要证明：对于我们构造出的网络，上面的任意一条可行流都和原来的二分图匹配一一对应。

\textbf{Proof.}$ 考虑如果有一个流量在我们的方案中出现，例如 $S\rightarrow u\rightarrow v\rightarrow T$，他就可以理解成 $u$ 和 $v$ 形成了一个合法的匹配。注意到这个时候，我们可以满足一个点最多和一个点匹配的性质，因为 $S\rightarrow u$ 的容量是 $1$（其中 $u$ 不妨设他是一个左部点），所以 $u$ 不可能和另外两个匹配，不然就不满足流量守恒的性质。同理，右边的点也最多和一个左边的点形成匹配。所以我们的流对应的这一个匹配方案一定是合法的。$\square

当然，我们也可以规定一个点可以和 k_i 个点形成匹配，这样我们只要把 S\rightarrow u 的边权改成 k_i 就行，证明方法和上面几乎完全相同，不再赘述。

习题 P2756 飞行员配对方案问题

const int N = 110, M = 5210, INF = 1e18;

int m, n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

int dinic(); // dinic 模板省略 

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    S = 0, T = n + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ ) add(S, i, 1);
    for (int i = m + 1; i <= n; i ++ ) add(i, T, 1);
    int a, b;
    while (cin >> a >> b && a != -1) add(a, b, 1);
    cout << dinic() << "\n";
    for (int i = 0; i < idx; i += 2)
        if (e[i] > m && e[i] <= n && !f[i])
            cout << e[i ^ 1] << " " << e[i] << "\n";
    return 0;
}

习题 P3254 圆桌问题

#define int long long

const int N = 430, M = (150 * 270 + N) * 2, INF = 1e18;

int m, n, S, T;
int h[N], e[M], ne[M], f[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c);
int dinic();

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    S = 0, T = m + n + 1;
    memset(h, -1, sizeof h);
    int tot = 0;
    for (int i = 1, c; i <= m; i ++ )
    {
        cin >> c;
        add(S, i, c);
        tot += c;
    }
    for (int i = 1, c; i <= n; i ++ )
    {
        cin >> c;
        add(m + i, T, c);
    }
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= n; j ++ )
            add(i, m + j, 1);
    if (dinic() != tot) cout << "0\n";
    else 
    {
        cout << "1\n";
        for (int i = 1; i <= m; i ++ )
        {
            for (int j = h[i]; ~j; j = ne[j])
                if (e[j] > m && e[j] <= m + n && !f[j])
                    cout << e[j] - m << " ";
            cout << "\n";           
        }
    } 
    return 0;
}

习题 P2763 试题库问题

const int N = 2010, M = 44000, INF = 0x3f3f3f3f;

// 模板略去

signed main()
{
    cin >> m >> n, S = 0, T = n + m + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) add(S, i, 1);
    for (int i = 1, w; i <= m; i ++ )
        cin >> w, k += w, add(i + n, T, w);
    for (int p, id, i = 1; i <= n; i ++ )
    {
        cin >> p;
        for (int j = 1; j <= p; j ++ )
            cin >> id, add(i, id + n, 1);
    }
    int res = dinic();
    if (res != k) puts("No Solution");
    else
    {
        for (int id = 1; id <= m; id ++ )
        {
            cout << id << ":";
            for (int i = h[id + n]; ~i; i = ne[i])
            {
                int j = e[i];
                if (f[i] && j <= n) cout << " " << j;
            }
            cout << "\n";
        }
    }
    return 0;
}

相信通过上述习题，大家已经对最大流解决二分图匹配的相关问题非常清晰了。

最小路径覆盖

最大流还有一个应用，可以用来解决 DAG 上的最小路径覆盖问题。请读者分析如下例题，先稍作思考，若无思路再阅读后文中的题解。

例题 P2764 最小路径覆盖问题

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

这题我们可以使用调整法。我们假设，一开始，我们用 n(|V|=n) 条路径来覆盖，一条路径就是一个孤立点。因为每次合并两条路径，图中的路径覆盖数量就会 -1，所以我们希望合并尽可能多的路径，即将两个路径通过一条边首尾相连。所以我们只需要利用网络流合并相关的路径即可。

我们可以使用拆点的方法处理。

将每个点拆开，拆成 x_i, y_i 两个点，从源点向 x_i 连边，容量为 1；对于原图中的每条边 (u, v) ，从 x_u 向 y_v 连边，容量为 1；从 y_i 向汇点连边，容量为 1。这样每一条增广路都只会经过 2 个节点 (x_u, y_v)，对应合并的两个节点。此时的最大流对应的就是最多可以合并的路径数。

具体证明过程：我们思考一次增广代表着什么。增广的时候，相当于找到一条从左部点 s 到右部点 t 的长为奇数的交错路径，也就是二分图匹配中的增广路（交错路径由未匹配边——匹配边——未区配边交错构成，若交错路径长度为 2l+1，第奇数条边为未匹配边，第偶数条边为匹配边，未匹配边比匹配边多一条，只是网络流中的匹配边是满流边的反向边），而找到一条增广路相当于将所有满流边的反向边（即匹配边）所连接两条路径之间的合并关系取消，无流边（即未匹配边）所连接的两条路径合并，又因为末匹配边比匹配边多一条，那么这样就可以保证每次增广都能多合并一组路径，每次使路径条数减少 1。那么说明只要我们求出的是最大流（最大匹配），那么一定是使得合并的路径最多。

那么，方案可以如何输出呢？如何通过残量网络暴力构造？

首先我们需要找出所有的起点，什么样的点会是起点？如果对于右部点 u，存在满流边 (v, u)，那么说明 v 在所选出的某条路径上肯定是 u-n 的前驱（因为在最大流过程中合并了以 v 结尾和以 u-n 开头的路径），u-n 就肯定不是路径的起点。所以如果 u-n 是路径的起点，那么没有流量经过点 u ，也就是说边 (u, T) 流量为 0。于是所有满足 (i+n, T) 流量为 0 的点 i 都是路径起点。

确定了路径起点，我们就来解决对于某个特定起点 i 如何找以 i 为起点的路径。如果边 (i, j) 是满流边，那么说明点 j-n 在路径上是点 i 的后继。所以我们只需要对于 i 找出这样的 j，然后再以 j-n 为起点往后找满流边所连接的后继（对于每个 i，这样的 j 肯定也是唯一的，因为二分图中我们每条正向边的容量都只有 1）。记得在 DFS 的时候先输出点 i 并且把路径上的所有点都打上标记防止反复输出（以保证路径不交）。

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

#define int long long

const int N = 2010, M = 44000, INF = 0x3f3f3f3f;

int m, n, S, T, k;
int h[N], e[M], f[M], ne[M], idx = 1;
int q[N], d[N], cur[N], ed[N];
bool st[N];

void add(int a, int b, int c)
{
    e[ ++ idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx;
    e[ ++ idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx;
}

// 模板略去 

void write_path(int u)
{
    cout << u << ' ';
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j > n && j <= 2 * n && !f[i] && !st[j - n])
            write_path(j - n);
    }
}
signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1, a, b; i <= m; i ++ )
        cin >> a >> b, add(a, b + n, 1);
    S = 2 * n + 1, T = 2 * n + 2;
    for (int i = 1; i <= n; i ++ )
        add(S, i, 1), add(i + n, T, 1), ed[i + n] = idx - 1;
    int res = n - dinic();
    for (int i = n + 1; i <= 2 * n; i ++ )
        if (f[ed[i]] == 1) write_path(i - n), cout << "\n";
    cout << res << "\n";
    return 0;
}

例题 P2765 魔术球问题

假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,\cdots 的球：

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

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

试设计一个算法，计算出在 n 根柱子上最多能放多少个球。例如，在 4 根柱子上最多可放 11 个球。

对于给定的 n，计算在 n 根柱子上最多能放多少个球。1\le n\le 55 .

考虑，如果已经知道要放 m 个球，如何求出需要多少根柱子呢？非常简单，对于 \forall i<j,(i,j)\in ([1,m],[1,m]),i+j\in \{x~\vert~\exists k\in \mathbb{Z},k^2=x\} 在原图上连一条 i\longrightarrow j 的边即可，边权为 1，此时最小路径覆盖的条数就等于需要的柱子根数。当然在新图上怎么连，参考上述介绍模型。

现在问：n 根柱子上最多能放多少个球。显然，因为 n\le 55，所以最多可以放的球的数量不会很多。考虑不断往其中加球，直到再加一个就会导致最小路径覆盖的条数 >n 时，就终止循环，然后根据上述方式构造方案。

如果数据范围变大，可以二分答案优化。但是此处直接暴力可过。

因为笔者在写代码的时候把 dinic 函数作了极小的修改，所以在此给出完整的代码。

#define int long long

const int N = 40010, MM = 1000010, INF = 0x3f3f3f3f, M = 20000;

int m, n, S = 2 * M + 1, T = 2 * M + 2, nodes, r, thres = -1; 
int h[N], e[MM], f[MM], ne[MM], idx;
int q[N], d[N], cur[N], ed[N];
bool st[N];

bool check(int x)
{
    int t = sqrt(x);
    if (t * t != x && (t + 1) * (t + 1) != x) return 0;
    return 1;
}

void add(int a, int b, int c)
{
    e[ ++ idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx;
    e[ ++ idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T)  return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;  // 当前弧优化
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

void write_path(int u)
{
    cout << u << ' ';
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j > M && j <= 2 * M && !f[i] && !st[j - M])
            write_path(j - M);
    }
}

bool add(int i)
{
    add(S, i, 1), add(i + M, T, 1), ed[i + M] = idx - 1;
    for (int j = 1; j < i; j ++ )
        if (check(i + j)) add(j, i + M, 1); 
    return i - dinic() <= n;
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    memset(h, -1, sizeof h); idx = 1; memset(ed, -1, sizeof ed);
    for (int i = 1; ; i ++ ) if (add(i)); else { thres = i - 1; break; }
    memset(h, -1, sizeof h); idx = 1; r = 0; memset(cur, -1, sizeof cur);
    for (int i = 1; i <= thres; i ++ ) add(i);
    cout << thres << "\n";
    for (int i = M + 1; i <= M + thres; i ++ )
        if (ed[i] != -1 && f[ed[i]] == 1) write_path(i - M), cout << "\n";
    return 0;
}

上下界可行流

上下界网络流本质是给流量网络的每一条边设置了流量上界 c(u,v) 和流量下界 b(u,v)。也就是说，一种可行的流必须满足 b(u,v) \leq f(u,v) \leq c(u,v)。同时必须满足除了源点和汇点之外的其余点流量平衡。

根据题目要求，我们可以使用上下界网络流解决不同问题。

我们先介绍无源汇上下界可行流。

给定无源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时每一个点流量平衡。

不妨假设每条边已经流了 b(u,v) 的流量，设其为初始流。同时我们在新图中加入 u 连向 v 的流量为 c(u,v) - b(u,v) 的边。考虑在新图上进行调整。

由于最大流需要满足初始流量平衡条件（最大流可以看成是下界为 0 的上下界最大流），但是构造出来的初始流很有可能不满足初始流量平衡。假设一个点初始流入流量减初始流出流量为 M。

若 M=0，此时流量平衡，不需要附加边。

若 M>0，此时入流量过大，需要新建附加源点 S'，S' 向其连流量为 M 的附加边。

若 M<0，此时出流量过大，需要新建附加汇点 T'，其向 T' 连流量为 -M 的附加边。

如果附加边满流，说明这一个点的流量平衡条件可以满足，否则这个点的流量平衡条件不满足。（因为原图加上附加流之后才会满足原图中的流量平衡。）

在建图完毕之后跑 S' 到 T' 的最大流，若 S' 连出去的边全部满流，则存在可行流，否则不存在。

习题 Acwing 2188 无源汇上下界可行流

#define int long long
const int N = 210, M = 21111, INF = 1e18;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], l[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c, int d);
int dinic();

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    S = 0, T = n + 1;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for (int i = 1; i <= n; i ++ )
        if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i];
        else if (A[i] < 0) add(i, T, 0, -A[i]);
    if (dinic() != tot) cout << "NO\n";
    else
    {
        cout << "YES\n";
        for (int i = 0; i < m * 2; i += 2)
            cout << f[i ^ 1] + l[i] << "\n";
    }
    return 0;
}

接下来考虑有源汇上下界可行流相关问题。原题如下：给定有源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。

对于这题，假设源点是 S，汇点为 T，我们只需要加入一条 T 到 S 的上界为 +\infty，下界为 0 的边转化为无源汇上下界可行流问题即可。

显然，若有解，则 S 到 T 的可行流流量等于 T 到 S 的附加边的流量。

对上述问题加强成有源汇上下界最大流：给定有源汇流量网络 G。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。如果存在，询问满足标定的最大流量。

我们找到网络上的任意一个可行流。

如果找不到解就可以直接结束；
如果有解，我们考虑删去所有附加边之后的残量网络并且在网络上进行调整。具体来说，我们在残量网络上再跑一次 S 到 T 的最大流，将可行流流量和最大流流量相加即为答案。

习题 Acwing 2189 有源汇上下界最大流

#define int long long

const int N = 210, M = 25000, INF = 1e18;

int h[N], e[M], f[M], ne[M], idx, A[N];
int q[N], d[N], cur[N];
int n, m, S, T, s, t;

void add(int a, int b, int c);
int dinic();

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m >> s >> t;
    S = 0, T = n + 1;
    while (m -- )
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, d - c);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for (int i = 1; i <= n; i ++ )
        if (A[i] > 0) add(S, i, A[i]), tot += A[i];
        else if (A[i] < 0) add(i, T, -A[i]);
    add(t, s, INF);
    if (dinic() < tot) cout << "No Solution\n";
    else
    {
        int res = f[idx - 1];
        S = s, T = t;
        f[idx - 1] = f[idx - 2] = 0;
        cout << dinic() + res << "\n";
    }
    return 0;
}

有源汇上下界最小流的做法和最大流类似。我们考虑将残量网络中不需要的流退掉，找到网络上的任意一个可行流。

如果找不到解就可以直接结束。
否则我们考虑删去所有附加边之后的残量网络，我们在残量网络上再跑一次 T 到 S 的最大流，将可行流流量减去最大流流量即为答案。

习题 Acwing 2190 有源汇上下界最小流

// 模板略去

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m >> s >> t;
    S = 0, T = n + 1;
    while (m -- )
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, d - c);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for (int i = 1; i <= n; i ++ )
        if (A[i] > 0) add(S, i, A[i]), tot += A[i];
        else if (A[i] < 0) add(i, T, -A[i]);
    add(t, s, INF);
    if (dinic() < tot) cout << "No Solution\n";
    else
    {
        int res = f[idx - 1];
        S = t, T = s;
        f[idx - 1] = f[idx - 2] = 0;
        cout << res - dinic() << "\n";
    }
    return 0;
}

其他应用

本节中将会讲解更多的最大流相关例题，以帮助读者理解最大流在算法竞赛中的应用。

例题 P2766 最长不下降子序列问题

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

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

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

如果允许在取出的序列中多次使用 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 问做法显然，f_i 表示以 i 为结尾的最长不下降子序列的长度，暴力 DP 即可。我们设最终算出来最长不下降子序列的长度为 k=\max_{i=1}^n f_i .

第 2 问中，看到 最多可以取出多少个不同的，结合数据范围 1\le n\le 500，很容易想到就是网络流。那么如何建图呢？

这个时候，有很多同学可以想到：我们不妨以 DP 过程中的转移为参照连边 . 一个数可以作为起点，当且仅当 f_i=1；一个数可以作为终点，当且仅当 f_i=k . 结合上面的分析，有些人就会给出如下建图：

建立虚拟源点和汇点 S,T。
对于所有 f_i=1 的点 i，连一条 S\rightarrow i 的边，容量为 1。
对于所有 f_i=k 的点 i，连一条 i\rightarrow T 的边，容量为 1。
对于每对 i,j(i>j)，当 a_i\ge a_j 且 f_i=f_j+1 时，即 j 是 i 的最佳转移点（之一）时，从 j\rightarrow i 连一条容量为 1 的边。则 S\rightarrow T 的最大流即为答案。

这看上去很有道理，但是存在一个非常严重的问题：一个点的出流可能不止是 1。

我们举一个例子：当 a_1=5,a_2=4,a_3=11,a_4=45,a_5=14 的时候，f=\{1, 1, 2, 3, 3\}。根据上述的建图，读者可以自行在纸上推算一下，可以连出这几条边（容量均为 1）：S\rightarrow a_1,S\rightarrow a_2,a_1\to a_3,a_2\to a_3,a_3\to a_4,a_3\to a_5, a_4\to T,a_5\to T。不难发现，如果在这张图上进行 Dinic 算法的话，会有以下两条增广路都会对答案产生 1 的贡献：S\rightarrow a_1\rightarrow a_3\to a_4\to T, S\to a_2\to a_3\to a_5\to T。所以他的最大流是 5，但是显然，我们只能从 \{5,4,11,45,14\} 中取出一条不下降子序列啊！

如果你理解了上述内容，就很容易发现问题所在：我们没有办法通过改变容量限制直接增加对点的流量限制。什么意思呢？比如说在刚刚我们举的例子里面，尽管所有的边容量都是 1，但是经过 3 这个点的流量还是 2，题目却要求每个点只能选择一次，相当于是经过 3 这个点的流量最多是 1。

讲到这里，正解也就呼之欲出了：我们考虑拆点！相当于，我们把每一个点在网络中用一条边来表示，这样我们就可以通过修改这一条边的容量来表示这一个点的流量限制了。

我们先在上述例子中演示一下，再给出形式化的描述。假设点 i 被拆成了 i_x,i_y 这两个点。

那么因为每一个点最多被选择一次，也就是流量最多是 1，所以我们对于 i=1,2,3,4,5，分别连一条 i_x\rightarrow i_y 的边，容量为 1。从 S 连出的边中，不妨我们直接把 S 连向左边的点；连向 T 的边中，考虑直接把右边的点连向 T：S\rightarrow 1_x,S\rightarrow 2_x,4_y\to T,5_y\to T。

关键是转移的边，我们要规定一下边的方向顺序。因为刚刚我们是把 S 连向左边的点，把右边的点连向 T，那就说明：在我们最终建出来的网络中，转移到 i 的流量应该是流向 i 的左边的点的，转移出 i 的流量应该是从右边的点连出的。换句话说，如果我们在原来的网络中有 j\rightarrow i 的转移，那么在这个完善的网络中，考虑连 j_y\rightarrow i_x，这样就完美刻画了所有条件。在上面的例子中，相当于就是 1_y\rightarrow 3_x,2_y\to 3_x,3_y\to 4_x,3_y\to 5_x .

现在我们已经分析出了建图的方式了，我们汇总一下，得出一个对建图的形式化表达：

从 S 向每个 f_i=1 的 i_x 点建边，容量为 1；
从每个 i_x 向 i_y 建边，容量为 1；
对于每对 i, j(i>j) ，当 a_i\ge a_j 且 f_i=f_j+1 时，从 j_y 向 i_x 建边，容量为 1；
从 f_i=k 的 i_y 向汇点建边，容量为 1 ．

终于，我们分析完了第 2 问。那第 3 问，允许在取出的序列中多次使用 x_1 和 x_n（其他元素仍然只允许使用一次）。如果你充分理解了上面的内容，就很容易发现：刚刚我们为了限制最多只能使用一次，进行了拆点；那现在可以多次使用 x_1 和 x_n 的时候，我们只要把 1_x\rightarrow 1_y,n_x\rightarrow n_y 的边权都改成 +\infty 不解决了？

如果只改这两条边显然是有问题的，因为 S\to 1_x 本身就只流了 1 的流量，1_x\to 1_y 的容量改的再大也没用，因为流过去的最多还是只有 1；n_x\rightarrow n_y 也是同理的，就算你在 n_y 堆积了再多的流量，也迫于 n\to T 的容量为 1 的限制，只能流过去 1。所以我们只要把 S\to 1_x,n_y\to T 的容量也改成 +\infty 就可以了。

所以第 3 问本质上就是在第 2 问的基础上，把 1_x\to 1_y,n_x\to n_y,S\to 1_x,n_y\to T 边的容量都改成 +\infty（如果边存在的话就修改，否则不管），再跑最大流即为答案。这样就做完了。

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

const int N = 10010, M = 2 * N, INF = 1e12;

int n, m, S, T, a[N], dp[N];

// 模板略过 

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    int k = 0;
    for (int i = 1; i <= n; i ++ )
    {
        dp[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1);
        k = max(k, dp[i]);
    }
    cout << k << "\n";
    if (k == 1)
    {
        cout << n << "\n" << n;
        return 0;
    }
    memset(h, -1, sizeof h);
    S = 0, T = 2 * n + 1;
    for (int i = 1; i <= n; i ++ ) 
        if (dp[i] == 1) add(S, i, 1);
    for (int i = 1; i <= n; i ++ )
        if (dp[i] == k) add(i + n, T, 1);
    for (int i = 1; i <= n; i ++ ) add(i, i + n, 1);
    for (int j = 1; j <= n; j ++ )
        for (int i = j + 1; i <= n; i ++ ) 
            if (a[i] >= a[j] && dp[i] == dp[j] + 1) add(j + n, i, 1);
    cout << dinic() << "\n";
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        if (dp[i] == 1)
        {
            if (i == 1) add(S, i, INF);
            else add(S, i, 1);
        }
    for (int i = 1; i <= n; i ++ )
        if (dp[i] == k)
        {
            if (i == n) add(i + n, T, INF);
            else add(i + n, T, 1);
        }
    add(1, 1 + n, INF), add(n, 2 * n, INF);
    for (int i = 2; i < n; i ++ ) add(i, i + n, 1);
    for (int j = 1; j <= n; j ++ )
        for (int i = j + 1; i <= n; i ++ ) 
            if (a[i] >= a[j] && dp[i] == dp[j] + 1) add(j + n, i, 1);
    cout << dinic() << "\n";
    return 0;
}

例题有 n 个盒子，第 i 个盒子有 a_i 个颜色为 i 的球。你需要依次执行 m 个事件 \left(x_i, y_i\right) 。对于每个事件，你可以拿一个盒子 x_i 和一个盒子 y_i 中的球交换，也可以不交换。最大化所有事件后 1 号盒子中球的颜色数。n, m, a_i \leq 3000 .

考虑求出一个 1 号盒中球的可重集是否可达，将这些球的初始位置染黑，剩余球染白即可。

进一步地，同一类的球只需要一个，所以可以将每个盒子放入 1 个黑球和 a_i-1 个白球，最大化 1 号盒子中黑球的个数即可。这样交换操作就只能是将盒子中黑球的数量 \pm 1 ，直接建图描述每一次可能的交换即可。

例题 AGC037D

注意到初始 A 、目标 D 都为已知，因此就可以依靠这种定的关系建图。如果我们想知道方案，对于每个元素我们就要知道其在 B 或 C 中的行号、列号和值。

考虑 A 和 B 的关系：我们发现，A 和 B 每一整行的元素一定是相同的（不考虑顺序），因此在图中可以使用相同的节点表示 A 和 B 的行号（ C 和 D 同理）。

考虑 B 和 C 的关系：我们发现，B 和 C 每一整列的元素一定是相同的，因此在图中可以使用相同的节点表示 B 和 C（当前列）的值。

左边 3 个点表示 A 和 B 的行号，右边 3 个点表示 C 和 D 的行号，中间 6 个点则表示 B 和 C 的值。

因为 A 到 B 每行的元素相同，所以从 A 每行的行号向 B 每行（也就是 A 每行）的值连容量为 1 的边，表示 B 当前行可以存在 A 当前行的值。

因为 C 到 D 每行的元素也相同，所以 D 当前行的行号应从 C 当前行的所有值连容量为 1 的边，表示 C 当前行可以存在 D 当前行的值。

我们现在倒回来看看连完后的图代表着什么，例如一条路径： 1 \sim 6 \sim 3 就表示 B 中第一行值为 6 的元素在 C 中的第三行（值为 6 的元素在 B 中第一行，在 C 中第三行）；路径： 3 \sim 5 \sim 3 表示 B 中第三行值为 5 的元素在 C 中还是第三行。

一组（3 条且没有公用节点）路径如： 1 \sim 6 \sim 3 、 2 \sim 3 \sim 2 、 3 \sim 1 \sim 1 就表示 B 、 C 的这一列的元素为 6 、 3 、 1 。图中可以分出两组路径，刚好就对应了矩阵的两列。

现在我们只需要知道如何给路径分组就能通过代入以上两个结论确定 B 和 C 的具体元素了。

那么如何分组呢？我们发现如果给原图加上源点和汇点，那么一组恰好对应一个完美匹配。于是跑 m 次网络流，每次根据满流的边统计答案即可。

注意统计答案的时候有多种写法，最简单的方法是枚举 A 的行号所对应的点和 D 的行号所对应的点，然后考虑其到中间的表示值的点的边，如果满流就可以在答案中标记；当然也可以直接枚举中间表示值的点，判断到两边的点是否流过了流量，计入答案即可。

[!TIP]

写的时候要注意以下两点：第一，在统计答案的时候，已经遍历过的点不能重复统计；第二，每一轮最大流结束之后，一定要彻底删除所有满流的边、清空反向边的容量，并恢复残留网络上源点、汇点所有出边 / 入边的容量为 1。这是因为，源点和汇点本身起到的作用就是约束 路径的分组过程，所以要把容量改回 1，但是其他满流的边的目的本身就是 在路径的分组中作为路径的一部分，所以不能重复利用。

在删除所有满流的边时，可以用这样的方式：注意到原网络中的边如果满流的话，容量就一定为 0 了，不需要进行任何处理就已经「自动清零」了。所以这个时候，只要清空所有反向边的容量，不仅可以规避掉 增广路径经过这一轮没有容量但是上一轮容量没有清空 的情况，而且还可以 彻底删除所有满流的边以及他的反向边。在下面提供的参考程序中，v 用于存储原图中所有反向边的编号。

参考程序中，1\sim n 分别是 A 矩阵的行号所对应的点，(n+1)\sim (n\times m+n) 分别是矩阵中的值所对应的节点，(n\times m+n+1)\sim (n\times m+2n+1) 分别是 D 矩阵的行号所对应的点。

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

const int K = 510, N = 1000010, M = 2 * N, INF = 1e18;

int n, m, S, T;
int a[K][K], resa[K][K], resb[K][K];
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
bool st[M];
vector<int> v;

void add(int a, int b, int c) 
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    v.push_back(idx);
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

// 模板略去

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) cin >> a[i][j];
    S = 0, T = n * m + 2 * n + 1;
    for (int i = 1; i <= n; i ++ ) add(S, i, 1);
    for (int i = n * m + n + 1; i <= n * m + 2 * n; i ++ ) add(i, T, 1);
    int topidx = idx - 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            add(i, a[i][j] + n, 1), add(a[i][j] + n, n * m + n + (a[i][j] - 1) / m + 1, 1);
    for (int i = 1; i <= m; i ++ )
    {
        for (int j = 0; j <= topidx; j += 2) f[j] = 1, f[j ^ 1] = 0;
        dinic();
        for (int u = 1; u <= n; u ++ )
            for (int j = h[u]; ~j; j = ne[j])
                if (!st[j] && f[j] == 0 && e[j] != S) st[j] = 1, resa[u][i] = e[j] - n;
        for (auto j : v) f[j] = 0;
    }
    for (int i = 1; i <= n; i ++ , cout << "\n")
        for (int j = 1; j <= m; j ++ ) cout << resa[i][j] << " ";
    for (int L = 1; L <= m; L ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j < n; j ++ ) 
                if (resa[j][L] > resa[j + 1][L]) swap(resa[j][L], resa[j + 1][L]);
    for (int i = 1; i <= n; i ++ , cout << "\n")
        for (int j = 1; j <= m; j ++ ) cout << resa[i][j] << " ";
    return 0;
}

例题 CF2038H

第 1 天的执政党当然 1 票。设第 i 天执政党编号为 p_i ，票数为 \text{val}_i ：

若 p_{i+1}<p_i ，可知 \text{val}_{i+1}=\text{val}_i 。
若 p_{i+1}=p_i ，可知 \text{val}_{i+1}=\text{val}_i 。
若 p_{i+1}>p_i ，可知 \text{val}_{i+1}=\text{val}_i+1 。

所以执政党票数知道了，其它党就是编号 <p_i 的票数 \leq \text{val}_i-1，>p_i 的票数 >\text{val}_i 。S 向每天连容量为 1 的边，表示一个票。每个党连成一条链，表示加了时间维，每条边表示一天的限制。每天向每个非执政党这天的入点连容量为 1 的边，费用是相应代价。

特别地，党执政日的限制是 = ，可从入点（上一天的出点）向 t 连容量为 \text{val}_i 的边，S 向出点连 \text{val}_i 的边，入点和出点之间就不要有边了。

最大流需要是 m+\sum \text{val}_i 。

Hall 定理：设二分图的左部点为集合 X ，右部点为集合 Y, X 存在匹配当且仅当 X 的任意子集 S 都有它的邻节点个数 N(S) \geq|S| 。特别地，若 |X|=|Y| 则存在完美匹配。

例题 Gym105833F

设答案 k 行 n 列。对于前 l 列，设 x 在 a 中出现 C_{x, l} 次，则其要在 b 中出现至少 c_{x, l}=\left\lfloor\frac{C_{x, l}}{m} k\right\rfloor 次。不考虑每行都是排列的话，第 l 列放 c_{x, l}-c_{x, l-1} 个 x ，最后空着的位置放那些没放完的数。

基于此我们构造排列。

第 l 列向数字 x 连 c_{x, l} 条边，这是一张二分图，也是一张 k-正则图（每个节点的度数都是 k ）。

结论（正则二分图匹配）：k-正则二分图（左部点和右部点都有 n 个）可被分成 k 个完美匹配。

做 $k$ 次二分图最大匹配即可，每次做完后删边。 **例题** POJ2699 考虑枚举答案后如何进行 check。一个显然的结论：**$a$ 越大的选手越有可能成为 Strong King**。容易想到，我们建立两列节点，一列为比赛节点，一列为选手节点。$S$ 连向所有比赛节点，$T$ 连向所有选手节点即可。随后，对于每一个钦定的 Strong King，向所有他**必须赢**的比赛连一条边。对于赢不赢无所谓的比赛，可以连容量为 $1$ 的双向边。最后，只要判断最大流是否等于 $\binom{n}{2}$ 即可。 **例题** POJ 1149 有如下性质：**对于 $a<b$，若 $a,b$ 共有至少一把钥匙，则 $a$ 可以买到的猪，$b$ 也可以买到**。证明是显然的。一个暴力做法：把 $S$ 连向所有猪圈，容量为猪的个数；把所有人连向汇点，容量为 $+\infty$。对于共有至少一把钥匙的人连权值为 $+\infty$ 的边，再把一个人可开的所有猪圈向他连边。这样边数是 $\mathcal{O}(n^2)$ 级别的，不可接受。优化：顺次枚举每一把钥匙，对于每一把钥匙的持有者，只要在相邻的两个人之间连 $+\infty$ 的边即可。同时，将每个猪圈向持有他的编号最小的人连边。这时正确性显然具备。此时边数降为线性，可以通过。 ## 最小割 ### 基本概述注意：在下文算法的讲解中，源点和汇点的字母和上述略有不同。此处，用 $(S,T)$ 描述一个割，用 $s,t$ 表示汇点。对于一个网络 $G=(V,E)$，其割的定义为一种点的划分方式：将所有的点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。我们的定义割 $(S,T)$ 的容量 $c(S,T)$ 表示所有从集合 $S$ 到集合 $T$ 的边的容量之和，即 $\displaystyle c(S,T)=\sum_{u\in S,v\in T}c(u,v)$。当然我们也可以用 $c(s,t)$ 表示 $c(S,T)$。最小割就是求得一个割 $(S,T)$ 使得割的容量 $c(S,T)$ 最小。通常我们认为，$c$ 的值一定是非负数。 ### 求解方法如何求出一个网络的最小割呢？其实，有一个定理已经帮助我们解决了这个问题。最大流最小割定理指出，对于任意网络 $G = (V, E)$，其上的最大流 $f$ 和最小割 $\{S, T\}$ 总是满足 $|f| = ||S, T||$。没错，最大流就等于最小割，我们直接跑一边 dinic 即可。 > 题外话：可以发现，最大流最小割定理，等价于 FF 最大流思想的正确性。接下来，我们就来证明最大流最小割定理。 $\textbf{Lemma}.$ 对于网络 $G = (V, E)$，任取一个流 $f$ 和一个割 $\{S, T\}$，总是有 $|f| \leq ||S, T||$，其中等号成立当且仅当 $\{(u, v) | u \in S, v \in T\}$ 的所有边均满流，且 $\{(u, v) | u \in T, v \in S\}$ 的所有边均空流。下面证明 $\textbf{Lemma}$ . 通过以下推导： $$ \begin{aligned} |f| & = f(s) \\ & = \sum_{u \in S} f(u) \\ & = \sum_{u \in S} \left( \sum_{v \in V} f(u, v) - \sum_{v \in V} f(v, u) \right) \\ & = \sum_{u \in S} \left( \sum_{v \in T} f(u, v) + \sum_{v \in S} f(u, v) - \sum_{v \in T} f(v, u) - \sum_{v \in S} f(v, u) \right) \\ & = \sum_{u \in S} \left( \sum_{v \in T} f(u, v) - \sum_{v \in T} f(v, u) \right) + \sum_{u \in S} \sum_{v \in S} f(u, v) - \sum_{u \in S} \sum_{v \in S} f(v, u) \\ & = \sum_{u \in S} \left( \sum_{v \in T} f(u, v) - \sum_{v \in T} f(v, u) \right) \\ & \leq \sum_{u \in S} \sum_{v \in T} f(u, v) \\ & \leq \sum_{u \in S} \sum_{v \in T} c(u, v) \\ & = ||S, T|| \\ \end{aligned} $$ 为了取等，第一个不等号需要 $\{(u, v) \mid u \in T, v \in S\}$ 的所有边均空流，第二个不等号需要 $\{(u, v) \mid u \in S, v \in T\}$ 的所有边均满流。原引理得证。因此，$\textbf{Lemma}$ 得证。现在我们只需证明对于任意网络，以上取等条件能被满足。假设某一轮增广后，我们得到流 $f$ 使得 $G_f$ 上不存在增广路，即 $G_f$ 上不存在 $s$ 到 $t$ 的路径。此时我们记从 $s$ 出发可以到达的结点组成的点集为 $S$，并记 $T = V \setminu\text{SS}$。显然，$\{S, T\}$ 是 $G_f$ 的一个割，且 $\displaystyle||S, T|| = \sum_{u \in S} \sum_{v \in T} c_f(u, v) = 0$。由于剩余容量是非负的，这也意味着对于任意 $u \in S, v \in T, (u, v) \in E_f$，均有 $c_f(u, v) = 0$。以下我们将这些边分为存在于原图中的边和反向边两种情况讨论： - $(u, v) \in E$：此时，$c_f(u, v) = c(u, v) - f(u, v) = 0$，因此有 $c(u, v) = f(u, v)$，即 $\{(u, v) \mid u \in S, v \in T\}$ 的所有边均满流； - $(v, u) \in E$：此时，$c_f(u, v) = c(u, v) - f(u, v) = 0 - f(u, v) = f(v, u) = 0$，即 $\{(v, u) \mid u \in S, v \in T\}$ 的所有边均空流。因此，增广停止后，上述流 $f$ 满足取等条件。根据引理指出的大小关系，自然地，$f$ 是 $G$ 的一个最大流，$\{S, T\}$ 是 $G$ 的一个最小割。$\square

问题如何输出最小割的任意一种方案？

答案我们可以通过从源点 s 开始 DFS，每次走残量大于 0 的边，找到所有 S 点集内的点。

问题如何最小化割边数量？

答案先求出最小割，把没有满流的边容量改成 +\infty，满流的边容量改成 1，重新跑一遍最小割就可求出最小割边数量；如果没有最小割的前提，直接把所有边的容量设成 1，求一遍最小割就好了。

算法应用

现在，我们已经可以求出一个网络的最小割了。那么这个算法在建模上面有哪些应用呢？

在思考经典运用之前，我们先看几个基础的思考题热身。

思考题 给定一张无向图，割 i 个点，使 s 到 t 不连通，求最少割点数。

解答对于割点问题，我们将一个点拆成两个。对于入边连接第一个点，对于出边连接第二个点，再加入一条第一个点到第二个点的带权有向边，权值为 1。对于其他边，边权设为 +\infty ，这样对拆点后图跑最小割即为结果。

思考题 有 n 个正整数，需要从中选出一些数，使这些数的和最大。若两个数 a,b 同时满足以下条件，则 a,b 不能同时被选：存在正整数 c，使 a^2+b^2=c^2，同时 \gcd(a,b)=1。其中 n\le 3000。

解答易证：奇数和奇数的平方和一定不是完全平方数，偶数和偶数的 \gcd 一定不为 1 . 然后就把所有的数分成奇数和偶数两个集合，从 s 连边到奇数，从偶数连边到 t ，中间同时满足条件的再连容量为 \infty 边即可。

二者选其一（集合划分）

例题一道经典题

有 n 个物品和两个集合 A,B，如果一个物品没有放入 A 集合会花费 a_i，没有放入 B 集合会花费 b_i；还有若干个形如 u_i,v_i,w_i 限制条件，表示如果 u_i 和 v_i 同时不在一个集合会花费 w_i。每个物品必须且只能属于一个集合，求最小的代价。

这是一个经典的 二者选其一 的最小割题目。我们对于每个集合设置源点 s 和汇点 t，第 i 个点由 s 连一条容量为 a_i 的边、向 t 连一条容量为 b_i 的边。对于限制条件 u, v, w ，我们在 u, v 之间连容量为 w 的双向边。

注意到当源点和汇点不相连时，代表这些点都选择了其中一个集合。如果将连向 s 或 t 的边割开，表示不放在 A 或 B 集合，如果把物品之间的边割开，表示这两个物品不放在同一个集合。

最小割就是最小花费。

此处有一个拓展：如果 i\to j 额外连了一条边权为 w 的边，就代表了当 i\in S,j\in T 同时满足时会额外有 w 的代价。

例题 SP839

给你一个无向图 G(V,E)。每个顶点都有一个 [0,2^{31}-1] 范围内的整数的标记 \text{mark}_i。不同的顶点可能有相同的标记。对于边 u,v，定义 \text{cost}(u, v)=\text{mark}_u \oplus \text{mark}_v，其中 \oplus 表示按位异或运算。

现在有 k 个点已经有 \text{mark} 了，你需要确定其他 n-k 个点的 \text{mark}，以使 \displaystyle \sum_{(u,v)\in E}\text{cost}(u,v) 尽可能小。如果有多解，请输出 \displaystyle\sum_{i=1}^n\text{mark}_i 最小的方案。如果仍有多解，输出任意一个。

多测，1 \leq T \leq 10,0<n \leq 500,0 \leq m \leq 3000,0 \leq \operatorname{mark}_i<2^{31}。

拆位，问题转化成每个点的 \text{mark} 为 0 或 1，要求最小化总花费。

注意到这张图可以被分为两个点集，对于一条边的两个端点，如果他们的值相同则没有贡献，否则对答案有 1 的贡献。我们只要最小化这个贡献即可。于是问题等价于：我们要把这 n 个点放入 1 集合或者 0 集合，连通这两个集合的边的权值和就是贡献和，我们需要最小化这个贡献，显然这是一个最小割模型。

建图方式如下：首先对题目中给出的所有边建立无向边，容量都为 1。对于 k 个已经有标记的点，如果当前二进制位为 1，那么向源点 S 连一条容量为 +\infty 的边；否则向汇点 T 连一条容量为 +\infty 的边。

接下来对这张图求最小割，割边显然都是原边。求得的最小割即为当前二进制位的最优解。考虑如何计算 \text{mark} 值，我们只要从 S 开始遍历所有满流的边，这些点在当前二进制位上的值均为 1。

#define int long long

const int N = 10010, M = 20010;
const int INF = 1e12;

int n, m, S, T, k, nd[N], mark[N];
int u[N], v[N];
int h[N], e[M], f[M], ne[M], idx, res[N];
int q[N], d[N], cur[N];
bool st[N];

void add();
int dinic();

void dfs(int u, int add)
{
    st[u] = 1, res[u] += add;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (f[i] && !st[j]) dfs(j, add);
    }
} 

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int TT;
    cin >> TT;
    while (TT -- )
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i ++ ) cin >> u[i] >> v[i];
        memset(res, 0, sizeof res);
        cin >> k;
        for (int i = 1; i <= k; i ++ ) cin >> nd[i] >> mark[i];
        S = 0, T = n + 1;
        for (int wei = 0; wei < 31; wei ++ )
        {
            idx = 0;
            memset(h, -1, sizeof h), memset(st, 0, sizeof st);
            for (int i = 1; i <= m; i ++ )
                add(u[i], v[i], 1), add(v[i], u[i], 1);
            for (int i = 1; i <= k; i ++ )
                if (mark[i] >> wei & 1) add(S, nd[i], INF);
                else add(nd[i], T, INF);
            dinic();
            dfs(S, 1 << wei);
        }
        for (int i = 1; i <= n; i ++ ) cout << res[i] << "\n";
    }
    return 0;
}

思考变式 P1361 小 M 的作物

形式化题意：有 n 个物品，划分到两个集合 A, B 中，第 i 个物品划分到集合 A 收益 a_i ，划分到集合 B 收益 b_{i 。} 有 m 个组合，每个组合有 c_j 个人，若组合中的全部划分在 A 中，收益 w_{a _j} ，若全部划分在 B 中，收益 w_{b _j} 。求最大收益。

对于最大收益，我们可以考虑转化一下问题再用最小割。然后用总边权减去最小割，得到的就是最大收益。具体来说，第 i 个物品划分到集合 A 损失 b_i ，划分到集合 B 损失 a_i 。对于一个组合若全部划分在 A 中，损失 w_{b j} ，若全部划分在 B 中，损失 w_{a j} ，否则损失 w_{a _j}+w_{b_ j} 。这样即可求最小损失。

对于组合问题，一种很常见的思路就是将这个组合打包到一起（建立虚点）。具体来说建图方法是，在上一问建图的基础上，对每个组合增加两个虚点，两个虚点分别与 s, t 连边，虚点与组合内点连边权为无穷的边。

下图表示：若 1,2,3 是一个组合，建出图如下。

最大权闭合子图

在许多实际应用中，给出的有向图常常是一个有向无环图（DAG），闭合图的性质恰好反映了事件间的必要条件的关系：一个事件的发生，它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划，其中一些课程需要以另一些课程为基础，这就是给出了有向无环图。若给所有课程打分，最大权闭合图对应了获益最大或效率最高的选课计划，解决了这个问题，就可以容易地选出一个最合理的选课计划。

在另外一些实际应用中，给出的是一个一般有向图，即有可能出现圈。常见的例子就是工程分期，一个工程可能含有很多项目，项目之间也有依赖关系。有些项目是需要同期一起开发，互相依赖的（即出现圈）。这样，也可以利用最大权闭合图，将最先应该完成的项目选出来作为工程的第一期。

最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或 0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。

做法：建立超级源点 s 和超级汇点 t ，若节点 u 权值为正，则 s 向 u 连一条有向边，边权即为该点点权；若节点 u 权值为负，则由 u 向 t 连一条有向边，边权即为该点点权的相反数。原图上所有边权改为 \infty 。跑网络最大流，将所有正权值之和减去最大流，即为答案。

\textbf{Proof.}$ 每一个符合条件的子图都对应流量网络中的一个割。因为每一个割将网络分为两部分，与 $s$ 相连的那部分满足没有边指向另一部分，于是满足上述条件。这个命题是充要的。最小割所去除的边必须与 $s$ 和 $t$ 其中一者相连。因为否则边权是 $\infty$ ，不可能成为最小割。我们所选择的那部分子图，权值和 $=$ 所有正权值之和 $-$ 我们未选择的正权值点的权值之和 $+$ 我们选择的负权值点的权值之和。当我们不选择一个正权值点时，其与 $s$ 的连边会被断开；当我们选择一个负权值点时，其与 $t$ 的连边会被断开。断开的边的边权之和即为割的容量。于是上述式子转化为：权值和 $=$ 所有正权值之和 $-$ 割的容量。于是得出结论，最大权值和 $=$ 所有正权值之和 $-$ 最小割 $=$ 所有正权值之和 $-$ 最大流。$\square

直接看这个结论可能无法理解这个算法的本质，接下来我们考虑换一个角度理解。

如果我们选了 u 就一定要选 v 的话，我们考虑连一条从 u\to v 的权值为 -\infty 的边，然后跑出最大割。但是最大割我们求不了，所以可以把所有点权全部取负数，然后跑最小割。但是如果取完相反数之后点权是负的话，我们只需要把他和源汇点相连的两条边的权值都加上这个负点权的绝对值即可，相当于就是给出的上述建图方式。最后所有正权值之和 - 最大流，就相当于是最大流减去所有补上去的负点权的绝对值。这样就更容易理解了。

例题 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 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

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

使用上述模型解题：对于每个实验，连一条从 s 到实验，边权为实验利益的边，对于每个需要的仪器，连一条从实验到器材，边权为 +\infty 的边，最后对于每个仪器，连一条从器材到 t，边权为器材耗费的边。

按照上面建图，求最小割即最大流，然后用实验利益总和减去最大流即为最大净收益。

#define int long long

const int N = 30010, M = 2 * N, INF = 1e18;

// 模板略 

signed main()
{
    scanf("%lld%lld", &m, &n);
    memset(h, -1, sizeof h);
    S = 0, T = n + m + 1;
    int res = 0;
    for (int i = 1, x; i <= m; i ++ ) // 注意本题读入方式 
    {
        char c; scanf("%lld", &x);
        res += x;
        add(S, n + i, x);
        while (1)
        {
            scanf("%lld%c", &x, &c);
            add(n + i, x, INF);
            if (c == '\n' || c == '\r') break;
        }
    }
    for (int i = 1, w; i <= n; i ++ ) scanf("%lld", &w), add(i, T, w);
    res -= dinic();
    for (int i = 1; i <= m; i ++ ) if (d[i + n] > 0) printf("%lld ", i);
    printf("\n");
    for (int i = 1; i <= n; i ++ ) if (d[i] > 0) printf("%lld ", i);
    printf("\n%lld\n", res);
    return 0;
}

离散变量取值问题

感谢大佬的博客，在本节中很有参考价值。

这是最小割中非常经典的一个模型，也叫做 广义切糕模型。

有若干个变量，每个变量取值为 v_1,v_2,\ldots,v_n，现在要求所有变量的和最小（大），且不同变量的取值有某种限制。

先不考虑限制，考虑用最小割刻画这个问题。

如图所示，对每一个变量都建立 n+1 个点 X_1, X_2, \ldots, X_{n+1} ：

从 S 到 X_1 建立一条边权为 +\infty 的边；
从 X_{n+1} 到 T 建立一条边权为 +\infty 的边；
从 X_i 到 X_{i+1} 建立一条边权为 v_i 的边；
从 X_{i+1} 到 X_i 建立一条边权为 +\infty 的边。

这保证了，每个变量所构造出的一条链上，在最小割中 有且仅有 一条边被割掉，被割掉的边的边权就代表了我们为这个变量的取值。

为什么有且仅有一条边被割掉？
\textbf{Proof.}$ **$\textcolor{red}{\textbf{Part~1.}}$** **证明存在性**：如果没有边被割，那么显然存在 $S \rightarrow T$ 的路径，矛盾。如果不加反向边存在一个割一条边的割，加上反向边依然存在这个割。**$\textcolor{blue}{\textbf{Part~2.}}$ 证明必要性**：假设存在两条边被割，即 $X_i \rightarrow X_{i+1}$ 和 $X_j \rightarrow X_{j+1}(i<j)$ 。我们知道，对于一条最小割中的割边 $(u, v)$ ，在被割完的图中一定存在 $S \rightarrow u, v \rightarrow T$ 的路径（否则这条边不割也行）。那么我们可以得出存在路径 $S \rightarrow X_{j+1}, X_{i+1} \rightarrow T$ 。因为无穷的边不会被割掉，所以还存在路径 $X_{j+1} \rightarrow X_{i+1}$ ，所以存在 $S \rightarrow T$ 的路径，矛盾！$\square

知道了这样的基本模型，我们来看例题。

例题 P6054 开门大吉

我们转化到刚刚的模型上，这题的变量就是 n 个选手每个人做的题目编号。

有 n 个变量，每个变量 X 有 m 个取值，设变量 X 选取的取值编号为 f[X] \in[1, m] 。
有 y 条限制，形如对于两个变量 X, Y ，有 f[X] \geq f[Y]+k 。（ k 不一定是正数）
所有变量和最小。

我们考虑如何处理这个限制，事实上，如果要让 f[X] \geq f[Y]+k ，只需要对于所有 i=1,2, \ldots, m+1 ，从 Y_i 向 X_{i+k} 连边权为 \infty 的边即可。（如果 i+k<0 或者 i+k>m+1 就不连）。

下证算法的正确性。

\textbf{Proof.}$ 还是从最小割的角度出发考虑：如果变量 $Y$ 选择了第 $p$ 个，那么我们知道 $Y_1 \sim Y_p$ 被划分给了 $S$ ， $Y_{p+1} \sim Y_{m+1}$ 被划分给了 $T$ 。记得我们从 $Y_i$ 连出的边权为 $\infty$ 的边吗？我们知道，如果一个被划分给 $S$ 的点连出了一条边权为 $\infty$ 的边，那么这条边的终点一定也划分给 $S$（否则就割掉了一条边权为无穷的边）。因此，$X_1 \sim X_{p+k}$ —定划分给了 $S$ ，换句话说 $f[X] \geq p+k$，我们就完成了这个限制。（如果 $p+k<1$ ，那么 $X$ 任取，我们也没有限制到任何 $X$ 的取值，也成立）$\square

为了方便读者理解，下举有 3 套题 (m=3)，限制中的 k=-1 的例子。

若 f[Y]=3，那么我们知道 f[X]≥2，反应到割上就是 X_1,X_2 被强制划分给了 S 所在的集合。

这满足我们的限制。这样就可以更加直观地理解到其正确性。

由于浮点数的 Dinic 算法的实现和整数略有不同，所以这里给出完整的代码。

注意这里代码中有一个细节，注意这里的重要优化：当总流量已经超过设的阈值 +\infty 就说明答案肯定是 -1，直接退出即可 . 如果没有这个优化就会超时，具体见代码。

#define int long long

const int N = 50010, M = 200010;
const double INF = 1e15;

int n, m, S, T, p, y, c[N];
int h[N], e[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];

void add(int a, int b, double c)  // 添加一条边a->b，容量为c；同时添加一条反向边
{
    e[idx] = b; f[idx] = c; ne[idx] = h[a]; h[a] = idx ++ ;
    e[idx] = a; f[idx] = 0; ne[idx] = h[b]; h[b] = idx ++ ;
}

bool bfs()  // 创建分层图
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S; d[S] = 0; cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i] > 0)
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

double find(int u, double limit)  // 在残留网络中增广
{
    if (u == T || limit < 1e-10) return limit;
    double flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;  // 当前弧优化
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i] > 0)
        {
            double t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t; f[i ^ 1] += t; flow += t;
        }
    }
    return flow;
}

double dinic()
{
    double r = 0, flow = 0;
    while (bfs() && r < INF) // 注意这里的重要优化：当流已经超过 INF 就说明答案肯定是 -1，直接退出即可 .
        while (flow = find(S, INF)) r += flow;
    return r;
}

int get(int i, int j)
{
    return (i - 1) * (m + 1) + j + 1;
}

void solve()
{
    cin >> n >> m >> p >> y; 
    idx = 0;
    memset(h, -1, sizeof h);
    S = 0, T = (m + 1) * n + 1;
    for (int i = 1; i <= n; i ++ )
        add(S, get(i, 0), INF), add(get(i, m), T, INF);
    for (int i = 1; i <= p; i ++ ) cin >> c[i];
    for (int j = 1; j <= m; j ++ )
        for (int i = 1; i <= n; i ++ )
        {
            double v = 0, prod = 1, x;
            for (int k = 1; k <= p; k ++ )
                cin >> x, prod *= x, v += c[k] * prod;
            add(get(i, j - 1), get(i, j), v);
            add(get(i, j), get(i, j - 1), INF);
        } 
    while (y -- )
    {
        int i, j, k;
        cin >> i >> j >> k;
        for (int x = 0; x <= m; x ++ )
            if (0 <= x + k && x + k <= m)
                add(get(j, x), get(i, x + k), INF);
    }
    for (int i = 0; i <= (m + 1) * n + 2; i ++ )
        cur[i] = h[i];
    double t = dinic();
    if (t >= INF) cout << "-1\n";
    else cout << fixed << setprecision(4) << t << "\n";
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

模拟流和最大流最小割的相互转化

例题 ARC125E

我们从源点向每个零食连流量为 a_i 的边，每个零食向每个小孩连对应的流量为 b_i 的边，所有小孩向汇点连流量为 c_i 的边。

网络流求解类二分图匹配可以做到 \mathcal{O}(m \sqrt{n}) ，因为 m 太大了，所以显然不可行。

考虑转化为对于上面这张图求最小割。

我们发现，我们要割掉左边一些零食点集与 s 的连边，同理割掉右边一些人的点集与 t 的边，再割掉中间某些 b_i 的边。

我们可以将这个过程看成删掉左右两边某些点，再删掉中间的某些边，有一个非常妙的性质就是，删掉左右两边的某些点后，必须将没删掉的那些点之间的所有连边全部删除才能保证图不联通，因为对于每一个零食，都对每个人连了边。

设左边零食删去的点集为 A ，右边人删去的点集为 c ，那么答案就为下面式子的最小值：

\sum_{i \in A} a_i+\sum_{i \in C} c_i+\sum_{i \notin C} b_i(n-|A|)

进一步地，我们将式子后面的两坨改一下，变为求下面式子的最小值： $$ \sum_{i \in A} a_i+\sum_{i=1}^m \min \left(b_i(n-|A|), c_i\right) $$ 让我们感性理解一下，左边为删掉某些零食点集的贡献，右边为选枚举人的点集中的所有点，要么删掉这个人，要么删掉左边剩余零食点集与这个人的所有 $b_i$ 的边，由于要求最小割，所以取两者中的最小值保证图不联通。于是题目就变为快速求上面这个式子。首先我们枚举 $A$ 集合的大小，在当前大小下，肯定选择的点是 $s$ 与之连边 $a_i$ 最小的几个，于是先对 $a_i$排序。如何快速求式子右边那一坨，将 $\frac{c_i}{b_i}$ 求出来，设 $x_i=\frac{c_i}{b_i}$ ，这样当 $n-|A|=x_i$ 时，$b_i(n-|A|)=c_i$ ，当 $n-|A|<x_i$ 时，取 $b_i(n-|A|)$ ，当 $n-|A|>x_i$ 时，取 $c_i$（当然 $x_i$ 可能为小数，可以将 $x_i+1$ 向下取整）。接下来思路就很明确了，每次枚举到一个 $n-|A|$ ，后面那个式子有些保持不变，有些超过了临界点，改变了数值，所以以 $x_i$ 为第一关键字从小到大排序，求出 $b_i$ 与 $c_i$ 的前缀和，每次二分大于等于 $n-$ $|A|$ 的 $x_i$ 的位置，前面的还是 $b_i(n-|A|)$ ，后面的是 $c_i$ ，利用前缀和统计答案（这时 $x_i+1$ 就有用了，因为浮点数范围太小，$x_i+1$ 后二分到这个临界点随便取 $b_i$ 还是 $c_i$ 都是同样的结果）。 #### 其他应用 **例题** ARC107F 经典地，$\displaystyle\sum b_i,-\sum b_i \leq\left\lvert\sum b_i\right\rvert$ ，我们可以自己决定每个连通块的 $b_i$ 都取反或不取反。每个节点有三种选择，删除贡献 $-a_i$ ，不取反贡献 $b_i$ ，取反贡献 $-b_i$ ，大致是求最大割，限制是对于没被删掉的点之间有边的要求取反不取反相同。转而求最小割： - 若 $b_i \geq 0$ ，预支贡献 $b_i$ ，删除减贡献 $a_i+b_i$ ，不取反减贡献 $0$ ，取反减贡献 $2 b_i$ 。 - 若 $b_i<0$ ，预支贡献 $\left|b_i\right|$ ，删除减贡献 $a_i+\left|b_i\right|$ ，不取反减贡献 $2\left|b_i\right|$ ，取反减贡献 $0$ 。所以，$i_{\text {in }}$ 向 $i_{\text {out }}$ 连 $a_i+\left|b_i\right|$ ，若 $b_i \geq 0$ 则 $S$ 向 $i_{\text {in }}$ 连 $2 b_i$ ，若 $b_i<0$ 则 $i_{\text {out }}$ 向 $T$ 连 $2\left|b_i\right|$ ，答案就是 $\sum\left|b_i\right|$ 减最小割。注意这里还没加限制，即对于原图中的 $(u, v)$ ，要连 $u_{\text{out}} \rightarrow v_{\text{in}}$ 和 $v_{\text{out}} \rightarrow u_{\text{in}}$ 容量为 $+\infty$ ，这样的话在原图重就不存在 $S \rightarrow u_{\text{in}} \rightarrow u_{\text{out}} \rightarrow v_{\text{in}} \rightarrow v_{\text{out}} \rightarrow T$ ，即 $u, v$ 都没被删且取反不取反不相同的情况。 ## 费用流 ### 问题和算法简注费用流的问题陈述如下：给定一个网络 $G=(V, E)$ ，每条边除了有容量限制 $c(u, v)$ ，还有一个单位流量的费用 $w(u, v)$ 。当 $(u, v)$ 的流量为 $f(u, v)$ 时，需要花费 $f(u, v) \times w(u, v)$ 的费用。$w$ 也满足斜对称性，即 $w(u, v)=-w(v, u)$ 。则该网络中总花费最小的最大流称为 **最小费用最大流**，即在最大化 $\sum_{(s, v) \in E} f(s, v)$ 的前提下最小化 $\sum_{(u, v) \in E} f(u, v) \times w(u, v)$ . 一般来说，我们解决这种问题使用 SSP 算法。 SSP（Successive Shortest Path）算法是一个贪心的算法。它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。实现时，只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。接下来给出 SSP 算法正确性的证明： > $\textbf{Proof}.$ 我们考虑使用数学归纳法和反证法来证明 SSP 算法的正确性。设流量为 $i$ 的时候最小费用为 $f_i$ 。我们假设最初的网络上没有负圈，这种情况下 $f_0=0$ 。假设用 SSP 算法求出的 $f_i$ 是最小费用，我们在 $f_i$ 的基础上，找到一条最短的增广路，从而求出 $f_{i+1}$ . 这时 $f_{i+1}-f_i$ 是这条最短增广路的长度。 > > 假设存在更小的 $f_{i+1}$ ，设它为 $f_{i+1}^{\prime}$ 。因为 $f_{i+1}-f_i$ 已经是最短增广路了，所以 $f_{i+1}^{\prime}-f_i$ 一定对应一个经过至少一个负圈的增广路。 > > 这时候矛盾就出现了：既然存在一条经过至少一个负圈的增广路，那么 $f_i$ 就不是最小费用了。因为只要给这个负圈添加流量，就可以在不增加 $s$ 流出的流量的前提下，使 $f_i$ 对应的费用更小。 > > 综上，SSP 算法可以正确求出无负圈网络的最小费用最大流。$\square

性质：每次寻找最短路的时候，找出的最短路是凸的。

下面给出一段模板，用 EK 算法为基础实现费用流，可以通过 P3381 【模板】最小费用最大流 .

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

const int N = 5010, M = 100010, INF = 1e18;

int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx; 
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf); 
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[t]);
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
    flow = cost = 0;
    while (spfa())
    {
        int t = incf[T];
        flow += t, cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    for (int a, b, c, d; m -- ; )
    {
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
    }
    int flow, cost;
    EK(flow, cost);
    cout << flow << " " << cost << "\n";
    return 0;
}

下面另给出一份基于 dinic 的实现，更为高效。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 2 * N, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], ne[M], f[M], w[M], idx;
int cur[N];
int q[N], hh, tt, dist[N];
bool st[N];
int min_cost, max_flow;

void add(int a, int b, int c, int d)
{
    e[idx] = b, ne[idx] = h[a], f[idx] = c, w[idx] = d, h[a] = idx ++ ;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, w[idx] = -d, h[b] = idx ++ ;
}

bool spfa()
{
    for (int i = 1; i <= n; i ++ )
        dist[i] = INF, st[i] = false;
    dist[S] = hh = tt = 0, q[0] = S;
    cur[S] = h[S];
    st[S] = true;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i] && f[i])
            {
                dist[j] = dist[t] + w[i];
                cur[j] = h[j];
                if (!st[j]) st[j] = true, q[ ++ tt] = j;
            }
        }
    }
    return dist[T] != INF;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    st[u] = true;
    for (int i = cur[u]; ~i; i = ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if (!st[j] && dist[j] == dist[u] + w[i] && f[i])
        {
            int t = find(j, min(limit - flow, f[i]));
            if (!t) dist[j] = INF;
            min_cost += t * w[i], f[i] -= t;
            f[i ^ 1] += t, flow += t;
        }
    }
    st[u] = false;
    return flow;
}

void dinic()
{
    int flow = 0;
    while (spfa()) while (flow = find(S, INF)) max_flow += flow;
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
    }
    dinic();
    cout << max_flow << " " << min_cost << "\n";
    return 0;
}

大家可能有一个疑问：如果图存在负环，到底应该如何处理？

例题 P7173

为了消除负环，强制所有负权边 (x, y) 满流并统计这些负权边的费用。加入边 (y, x) 用于退流，其权值为边 (x, y) 权值的相反数，流量下界为 0 ，流量上界为 (x, y) 的容量，然后使用上下界网络流求解。

强制满流可以解释为加入流量上界为 f ，下界为 f ，费用为 v 的边 (x, y)。注意到这时 (x, y) 只需要统计一下，不需要实际添加。而反向边实际上是用来退流反悔的。

下面，给出形式化的加边过程。

注意下文中提及的边的＂容量＂代表该边的流量下界为 0 ，流量上界为容量。

读入边的信息 x, y, f, v 并根据边权分类讨论：
建立附加源汇点 \text{SS}, \text{TT} 并连边，具体地，对于点 i ：
加入容量为 \inf 的边 (T, S) ，在图上跑以 \text{SS} 为源点，\text{TT} 为汇点的最小费用最大流（求解有源汇最小费用可行流）。将可行流流量（最后加入的边 (T, S) 的流量）计入答案流量，将此次最小费用最大流的费用计入答案费用。
撤去所有与附加源汇点 \text{SS}, \text{TT} 相连的边和最后加入的边 (T, S) 。跑一次以 S 为源点，T 为汇点的最小费用最大流。将此次最小费用最大流的流量和费用计入答案流量和答案费用。

刚开始的强制满流可以保证任意时刻网络无负环。

答案流量为可行流流量与最小费用最大流流量之和，答案费用为强制满流的费用、可行流的费用与最小费用最大流的费用之和。

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

const int N = 5010, M = 100010, INF = 1e18;

int n, m, S, T, tot[N], minc;
int h[N], e[M], f[M], w[M], ne[M], idx; 
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf); 
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[t]);
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
    while (spfa())
    {
        int t = incf[T];
        flow += t, cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    for (int a, b, c, d; m -- ; )
    {
        cin >> a >> b >> c >> d;
        if (d >= 0) add(a, b, c, d);
        else add(b, a, c, -d), tot[a] -= c, tot[b] += c, minc += c * d;
    }
    add(T, S, INF, 0);
    int SS = n + 1, TT = SS + 1;
    for (int i = 1; i <= n; i ++ )
        if (tot[i] > 0) add(SS, i, tot[i], 0);
        else if (tot[i] < 0) add(i, TT, -tot[i], 0);
    int flow, cost; flow = cost = 0;
    swap(SS, S), swap(TT, T);
    EK(flow, cost); flow = 0;
    swap(SS, S), swap(TT, T);
    EK(flow, cost);
    cout << flow << " " << cost + minc << "\n";
    return 0;
}

算法应用

一般来说，如果题目要求求出最大的代价，常用的算法有动态规划、贪心等。

但是如果题目不具备最优子结构，贪心也没有明显的正确性，数据范围较小，我们就容易想到 费用流。

值得一提的是，在处理有源汇上下界最小费用最大流问题中，在有源汇上下界最大流的基础上加上每条边的费用，附加边以及 t \rightarrow s 边的费用都是 0 ，其余原有边的费用为 w_{x y}。

在可行流最小费用 + 最大流最小费用的基础上还需要加上 \sum_{(x, y) \in e} a_{x y} \times w_{x y}。

费用递增

首先，我们要掌握用费用递增的方法处理一些费用流问题。

由于一条边的费用是固定，即 f_{i j} \times a_{i j} ，如果需要其费用是关于流量的一个函数 f ，且该函数单调递增。

那么可以将边拆成若干条，起点和终点仍然保持不变，但是第 i 条边的费用为 f(i+1)-f(i) ，且容量为 1。

例题 CF863E

注意到每个位置 i 都只能有一个数，并且这个数在 \left[l_i, r_i\right] 之间，相当于位置 i 可以为 \left[l_i, r_i\right] 中的某个数贡献一次出现次数。

从这里可以想到网络流，由于最终每个数都要出现一次，考虑将原问题求的总代价作为费用，而最大流量设计为能有效安排的位置个数，这样保证了使用最小费用最大流可以在有解的情况下求出最小代价，当然，此时最大流是 n 。

考虑一下发现，上述过程对应的是源点向每个位置 i 连一条容量为 1 ，代价为 0 的边，每个位置 i 向数值 \left[l_i, r_i\right] 连一条容量为 1 ，代价为 0 的边。

由于每种数值 j 的出现次数决定了最终代价，考虑每个数值 j 向汇点连 n 条容量为 1 ，费用分别为 1^2-0^0, 2^2-1^2, 3^2-2^2, \cdots, n^2-(n-1)^2 的边。

区间覆盖

接下来，我们来学习区间 k 覆盖问题。

问题数轴上存在一些区间 \left(a_i, b_i\right) ，权重为 w_i ，需要在其中选取一些区间，使得数轴上任意一点不被超过 k 个区间覆盖，并且最大化选取区间的权值和。

由于区间范围较大，需要将区间端点进行离散化。

需要将数轴上的整数点连接起来，i-1 连向 i ，容量为 k ，费用为 0 ，同时建立源点和汇点，源点连向数轴开头，汇点连向数轴结尾。

在目前的网络进行最大流算法，显然每一条边都会有 k 流量，那么可以利用流量 \geq 0 的性质，流量代表该数还能被多少个区间覆盖。

那么如何才能表示选中一个区间，然后将区间内所有边的流量减一呢？

考虑区间 (l, r)，l 连向 r ，容量为 1 ，费用为 -w ，然后进行最小费用流，最后答案取反即可。（当然可以在连数轴上的边设置一个大数 M ，然后此处费用为 w ，最后答案减去 M~\times 数轴长度）

由于总流量为 k ，那么如果选择走区间连的边，那么区间内的边流量一定减一，这样就做到了限制。

例题 P7425

首先如果问题存在解的话，那么可以将坏的停机坪视作无限多，并且飞机要移动的话，一定从好的停机坪移动到坏的停机坪。

如果存在解，将坏的停机坪扩充，并不会影响答案，在原来限制条件下非法的解一定劣于答案。（这是在很多题目中的重要思想）

首先所有好的停机坪等价，坏的停机坪等价，好的转到好的，坏的转到坏的没有意义。如果是从坏的转到好的，由于在降落时已经登机，此时移动只会增加成本。

那么假设所有飞机都在坏的停机坪上，此时一架飞机有三种选择

在 [l, r] 时间上占用一个好的停机坪，收益为 x；
在时刻 l 占用一个好的停机坪，之后移动到坏的停机坪（由于无限，在任意合法时间内移动都行），收益 x-p x；
始终停留在坏的停机坪上，收益 0。

这就类似区间 k 覆盖问题，先将时间离散化，然后将时间轴连成一条链，随后按照如下方式建图，对于每一个飞机建一个点 u：

棋盘相关

关于棋盘的最优化问题，往往可以通过黑白染色，或者对于每一行每一列建点，转化为二分图相关模型。

例题 ABC231H

首先对于所有的行建出一个节点，作为二分图的左部点，将所有的列建出一个节点，作为二分图的右部点。

然后可以发现如果用网络流来看的话，每一个点都至少需要流过 1 的流量，那么我们需要强制某一个点流过至少 1 的流量，那么可以在对应原点和汇点之间连一条容量为 1 ，代价为 -\infty 的边.

那么连上容量为 \infty 代价为 0 的边，然后需要保证最终的流量一定为 n+m ，那么在 s \rightarrow t 之间连容量为 n+m 代价为 0 的边即可。

然后考虑棋子 (x, y) 在两边连边，x \rightarrow y 连容量为 1 代价为 w 的边。

例题 P4003

本题思路非常简单，黑白染色即可，连边时需要考虑这些边：格子之间的转移，管道转向，到源点和汇点的链接。

具体建图可以参照下图理解，蓝色和黄色的边分别表示从源点出和进入汇点的边，紫色和绿色的边表示管道转动时连接情况的转移，橙色的边表示水在不同的方格中转移。注意图片仅为示意，没有画出完整的点和边，具体建边实现时考虑即可。

下附部分建图代码，作者为 kele7，笔者也参与了调试。

int h(int x,int y,int d){return 4*((x-1)*m+y-1)+d;}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v[i][j];
        }
    }t=h(n,m,5);//s=0 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i+j)&1){
                if(v[i][j]&1)add(h(i,j,1),t,1,0);
                if(v[i][j]&2)add(h(i,j,2),t,1,0);
                if(v[i][j]&4)add(h(i,j,3),t,1,0);
                if(v[i][j]&8)add(h(i,j,4),t,1,0);
                if(__builtin_popcount(v[i][j])==3){
                    if(!(v[i][j]&1)){
                        add(h(i,j,1),h(i,j,2),1,1);
                        add(h(i,j,1),h(i,j,3),1,2);
                        add(h(i,j,1),h(i,j,4),1,1);
                    }else if(!(v[i][j]&2)){
                        add(h(i,j,2),h(i,j,1),1,1);
                        add(h(i,j,2),h(i,j,3),1,1);
                        add(h(i,j,2),h(i,j,4),1,2);
                    }else if(!(v[i][j]&4)){
                        add(h(i,j,3),h(i,j,1),1,2);
                        add(h(i,j,3),h(i,j,2),1,1);
                        add(h(i,j,3),h(i,j,4),1,1);
                    }else if(!(v[i][j]&8)){
                        add(h(i,j,4),h(i,j,1),1,1);
                        add(h(i,j,4),h(i,j,2),1,2);
                        add(h(i,j,4),h(i,j,3),1,1);
                    }
                }else if(__builtin_popcount(v[i][j])==2){
                    if((v[i][j]&1)&&(v[i][j]&4))continue;//check if it is straight 
                    if((v[i][j]&2)&&(v[i][j]&8))continue;
                    if(v[i][j]&1)add(h(i,j,3),h(i,j,1),1,1);
                    if(v[i][j]&2)add(h(i,j,4),h(i,j,2),1,1);
                    if(v[i][j]&4)add(h(i,j,1),h(i,j,3),1,1);
                    if(v[i][j]&8)add(h(i,j,2),h(i,j,4),1,1);
                }else if(__builtin_popcount(v[i][j])==1){
                    if(v[i][j]&1){
                        add(h(i,j,2),h(i,j,1),1,1);
                        add(h(i,j,3),h(i,j,1),1,2);
                        add(h(i,j,4),h(i,j,1),1,1);
                    }else if(v[i][j]&2){
                        add(h(i,j,1),h(i,j,2),1,1);
                        add(h(i,j,3),h(i,j,2),1,1);
                        add(h(i,j,4),h(i,j,2),1,2);
                    }else if(v[i][j]&4){
                        add(h(i,j,1),h(i,j,3),1,2);
                        add(h(i,j,2),h(i,j,3),1,1);
                        add(h(i,j,4),h(i,j,3),1,1);
                    }else if(v[i][j]&8){
                        add(h(i,j,1),h(i,j,4),1,1);
                        add(h(i,j,2),h(i,j,4),1,2);
                        add(h(i,j,3),h(i,j,4),1,1);
                    }
                }
            }else{
                if(v[i][j]&1)add(s,h(i,j,1),1,0);
                if(v[i][j]&2)add(s,h(i,j,2),1,0);
                if(v[i][j]&4)add(s,h(i,j,3),1,0);
                if(v[i][j]&8)add(s,h(i,j,4),1,0);
                if(i>1)add(h(i,j,1),h(i-1,j,3),1,0);//^
                if(j<m)add(h(i,j,2),h(i,j+1,4),1,0);//>
                if(i<n)add(h(i,j,3),h(i+1,j,1),1,0);//v
                if(j>1)add(h(i,j,4),h(i,j-1,2),1,0);//<
                if(__builtin_popcount(v[i][j])==1){
                    if(v[i][j]&1){
                        add(h(i,j,1),h(i,j,2),1,1);
                        add(h(i,j,1),h(i,j,3),1,2);
                        add(h(i,j,1),h(i,j,4),1,1);
                    }else if(v[i][j]&2){
                        add(h(i,j,2),h(i,j,1),1,1);
                        add(h(i,j,2),h(i,j,3),1,1);
                        add(h(i,j,2),h(i,j,4),1,2);
                    }else if(v[i][j]&4){
                        add(h(i,j,3),h(i,j,1),1,2);
                        add(h(i,j,3),h(i,j,2),1,1);
                        add(h(i,j,3),h(i,j,4),1,1);
                    }else if(v[i][j]&8){
                        add(h(i,j,4),h(i,j,1),1,1);
                        add(h(i,j,4),h(i,j,2),1,2);
                        add(h(i,j,4),h(i,j,3),1,1);
                    }
                }else if(__builtin_popcount(v[i][j])==2){
                    if((v[i][j]&1)&&(v[i][j]&4))continue;
                    if((v[i][j]&2)&&(v[i][j]&8))continue;
                    if(v[i][j]&1)add(h(i,j,1),h(i,j,3),1,1);
                    if(v[i][j]&2)add(h(i,j,2),h(i,j,4),1,1);
                    if(v[i][j]&4)add(h(i,j,3),h(i,j,1),1,1);
                    if(v[i][j]&8)add(h(i,j,4),h(i,j,2),1,1);
                }else if(__builtin_popcount(v[i][j])==3){
                    if(!(v[i][j]&1)){
                        add(h(i,j,2),h(i,j,1),1,1);
                        add(h(i,j,3),h(i,j,1),1,2);
                        add(h(i,j,4),h(i,j,1),1,1);
                    }else if(!(v[i][j]&2)){
                        add(h(i,j,1),h(i,j,2),1,1);
                        add(h(i,j,3),h(i,j,2),1,1);
                        add(h(i,j,4),h(i,j,2),1,2);
                    }else if(!(v[i][j]&4)){
                        add(h(i,j,1),h(i,j,3),1,2);
                        add(h(i,j,2),h(i,j,3),1,1);
                        add(h(i,j,4),h(i,j,3),1,1);
                    }else if(!(v[i][j]&8)){
                        add(h(i,j,1),h(i,j,4),1,1);
                        add(h(i,j,2),h(i,j,4),1,2);
                        add(h(i,j,3),h(i,j,4),1,1);
                    }
                }
            }
        }
    }while(spfa(s))ans1+=dfs(s,inf,0);
    (g[0].size()==ans1&&ans2!=0)?cout<<ans2:cout<<-1;
}

建图优化

如果把左部点的区间和右部点的区间中的所有点两两相连，可以使用线段树优化建图。但是如果是左部点前缀和右部点后缀连边的话，直接对左部点和右部点都分别建一条链，然后把左部点前缀的末尾和右部点后缀的头部两点相连，实现更为简单高效。

例题 CF818G

拆点，把每个位置拆成入点和出点，之间连一条容量为 1、费用为 1 的边，使它至多只能被用一次。从源点 S 向源点 S^{\prime} 连一条容量为 4 、费用为 0 的边，S^{\prime} 向每个入点连一条容量为 1、费用为 0 的边。汇点大致同理。然后每个出点向后面合法的入点连一条容量为 1 、费用为 0 的边，跑最大费用最大流。套路地，对于每个值，我们用一条链把它们串起来。

这样建图产生了 O\left(n^2\right) 条边，不可接受，考虑优化建图。

同余部分大致同理，对于每个模 7 的余数也建一条链，每个出点直接连向链上的黑点。