文章目录

网络流1. 算法分析1.1 基本概念1.1.1 网络1.1.2 可行流1.1.3 残量网络1.1.4 増广路1.1.5 割1.1.5.1 定义1.1.5.2 性质 1.2 最大流1.2.1 最大流之匹配问题1.2.1.1 最大流求二分匹配问题1.2.1.2 最大流之多重匹配问题 1.2.2 最大流之上下界可行流1.2.2.1 无源汇上下界可行流1.2.2.2 有源汇上下界最大流1.2.2.3 有源汇上下界最小流 1.2.3 最大流之多源汇最大流1.2.4 最大流之关键边1.2.5 拆点 1.3 最小割1.3.1 最大闭合权子图1.3.2 最大密度子图1.3.3 最小权覆盖集1.3.4 最大权独立集 1.4 费用流 2. 板子2.1 最大流2.1.1 最大流算法2.1.1.1 EK算法2.1.1.2 dinic算法 2.1.2 上下界可行流2.1.2.1 无源汇上下界可行流2.1.2.2 有源汇上下界最大流2.1.2.3 有源汇上下界最小流 2.2 最小割2.2.1 基本概念2.2.2 最大权闭合子图2.2.3 最大密度子图 2.3 费用流2.4 其他操作2.4.1 还原网络2.4.1 打印方案 3. 典型例题3.1 最大流3.1.1 二分图匹配3.1.2 上下界可行流3.1.2.1 无源汇上下界可行流3.1.2.2 有源汇上下界最大流3.1.2.3 有源汇上下界最小流 3.1.3 多源汇最大流3.1.4 关键边3.1.5 最大流判定3.1.6 拆点3.1.7 特殊建图 3.2 最小割3.2.1 直接应用3.2.2 最大权闭合图3.2.3 最大密度子图3.2.4 最小点权覆盖集3.2.5 最大点权独立集 3.3 费用流3.3.1 费用流之匹配问题3.3.2 费用流之最大权不相交问题3.3.3 费用流之网格图模型3.3.4 费用流之上下界可行流

网络流

1. 算法分析

1.1 基本概念

1.1.1 网络

网络是指一个有向图$G=(V,E)$ 每条边 $(u,v)\in E$ 都有一个权值 $c(u,v)$ ，称之为容量（Capacity），当 $(u,v)\notin E$ 时有 $c(u,v)=0$ 。 其中有两个特殊的点：源点（Source）$s\in V$ 和汇点（Sink） $t\in V,(s\ne t)$ 。

1.1.2 可行流

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

容量限制：对于每条边，流经该边的流量不得超过该边的容量，即$f(u,v)\le c(u,v)$斜对称性：每条边的流量与其相反边的流量之和为 0，即 $f(u,v)=-f(v,u)$流守恒性：从源点流出的流量等于汇点流入的流量，即 $\forall x\in V-\{s,t\},{\sum }_{(u,x)\in E}f(u,x)={\sum }_{(x,v)\in E}f(x,v)$

那么 $f$ 称为网络 $G$ 的流函数。对于 $(u,v)\in E$ ， $f(u,v)$ 称为边的 流量 ，$c(u,v)-f(u,v)$ 称为边的 剩余容量 。整个网络的流量为 ${\sum }_{(s,v)\in E}f(s,v)$ ，即 从源点发出的所有流量之和 。

1.1.3 残量网络

定义 首先我们介绍一下一条边的剩余容量 $c_f(u,v)$ （Residual Capacity），它表示的是这条边的容量与流量之差，即 $c_f(u,v)=c(u,v)-f(u,v) $ 。

对于流函数 $f$ ，残存网络 $G_f$ （Residual Network）是网络 $G$ 中所有结点 和剩余容量大于 0 的边构成的子图。形式化的定义，即 $G_f=(V_f=V,E_f=\left\{(u,v)\in E,c_f(u,v)>0\right\})$ 。

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

可以用如下式子代表残量网络中每条边的权值： $c_f(u,v)=c(u,v)-f(u,v)(u,v)\in E$（正向边为容量-流量, 代表了还可以流多少流量） $c_f(u,v)=f(v,u)(v,u)\in E$ （反向边为流量， 代表了多少正向流量可以反悔）

性质

设原网络的流为$f$, 残量网络里的流为$f^{\prime }$,如果$f^{\prime }$不为0，那么说明原网络的流$f$不是最大流；如果$f^{\prime }$为0，那么说明原网络的流$f$是最大流残量网络的可行流$f^{\prime }$+原网络的可行流$f$ = 原网络的另一可行流$f+f^{\prime }$

1.1.4 増广路

定义 在原图 $G$ 中若一条从源点到汇点的路径上所有边的 剩余容量都大于 0 ，这条路被称为增广路 性质 如果原图中存在可行流$f$,可以依照原图构建对应的残量网络$G_f$,当残量网络中不存在增广路时，可行流$f$为最大流。

1.1.5 割

1.1.5.1 定义

割：是网络中顶点的一个划分，把所有顶点划分成两个顶点集合S和T，其中源点$s$属于$S$，汇点$t$属于$T$，记作$cut(S,T)$。 割的割边 割的割边：如果一条弧的两个顶点一个属于顶点集$S$一个属于顶点集$T$，该弧为割$cut(S,T)$的一条割边。 正向/逆向割边 从$S$指向$T$的割边是正向割边；从$T$指向$S$的割边是逆向割边 割的容量 割的容量：所有正向割边的容量和，不同割的容量不同。 $cut(S,T)={\sum }_{u\in S}{\sum }_{v\in T}c(u,v)$ 最小割 所有割里面，割容量最小的那个 割的流量 割的流量：所有正向割边的流量和-反向割边的流量和 $f(S,T)={\sum }_{u\in S}{\sum }_{v\in T}f(u,v)-{\sum }_{u\in T}{\sum }_{v\in S}f(u,v)$

1.1.5.2 性质

如果$f$是网络中的一个流(不必须是最大流)，$cut(S,T)$是任意一个割，那么$f$的值等于该割中的正向割边的流量和与逆向割边的流量和之差。 1.1. 推论1：如果$f$是网络中的一个可行流，$cut(S,T)$是一个割，那么$f$的值不超过割$cut(S,T)$的容量。 1.2. 推论2：网络中的最大流不超过任何割的容量。在任何网络中，如果$f$是一个可行流，$cut(S,T)$是一个割，且$f$的值等于该割的容量，那么$f$是一个最大流，$cut(S,T)$是一个最小割（容量最小的割）。最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。最小割中，其正向割边的流量一定等于割的容量，且如果存在逆向割边的话，逆向流量为0，否则一定还可以增广。最小割可能不唯一。最小割唯一性的判断是先跑一遍最大流，然后在残留网络中分别从源点和汇点出发dfs，只有当该边还有流量可用时可以访问下一个顶点，最后如果所有顶点都访问了，那么就是唯一的，否则不唯一。

1.2 最大流

问题描述 求从源点流向汇点的最大可行流量（可以有很多条路到达汇点），就是我们的最大流问题。

1.2.1 最大流之匹配问题

1.2.1.1 最大流求二分匹配问题

建图 设一个源点S和一个汇点T，源点S向左部每个点连一条权值为1的边，右部每个点向T连一条权值为1的边。对于左部每个点，向右部对应点连一条权值为1的边。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QysCxTr7-1601723735399)(https://i.loli.net/2020/09/23/QNbpHje3GaiBc4r.jpg)]

判断是否有答案 把源点S向左部点所有点连边的边权加起来求和，然后判断这个和是不是等于最大流。如果等于，说明存在答案；不等于，说明不存在答案。

打印方案 可以遍历残量网络中每一条左部点到右部点的边，如果这条边的流量为0，那么说明对应的左部点和右部点被选择了。

1.2.1.2 最大流之多重匹配问题

建图 设一个源点S和一个汇点T，源点S向左部每个点连一条权值为r的边(r的值依据题目意思决定)，右部每个点向T连一条权值为k的边(k的值依据题目意思决定)。对于左部每个点，向右部对应点连一条权值为1的边。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-26VlxOxK-1601723735405)(https://i.loli.net/2020/09/23/QZftBwrcAvMyaeI.jpg)]

判断是否有答案 把源点S向左部点所有点连边的边权加起来求和，然后判断这个和是不是等于最大流。如果等于，说明存在答案；不等于，说明不存在答案。

打印方案 可以遍历残量网络中每一条左部点到右部点的边，如果这条边的流量为0，那么说明对应的左部点和右部点被选择了。

1.2.2 最大流之上下界可行流

1.2.2.1 无源汇上下界可行流

    记原图为$G$, 构造的新图为$G^{\prime }$,可以证明通过如下的构造方式得到的$G^{\prime }$和原图一一对应：     对于每个点，计算其A[i] = 入边权值和-出边权值和（这里的入边和出边都指的是下界）。如果对于当前点的 A[i] = 入边权值和-出边权值和 > 0, 那么源点S向i点连一条权值为A[i]的边；如果A[i]<0,那么i点向汇点T连一条权值为-A[i]的边。对于原图$G$中的其他边，其上界为c，下界为d，那么在$G^{\prime }$中对应的边为d-c。     只有当S向每个i点连的边全部跑满时$G$和$G^{\prime }$才会一一对应，也就是说只有跑满时才会有答案。 原图$G$中的可行流为新图$G^{\prime }$中的可行流对应边+其下界c。

1.2.2.2 有源汇上下界最大流

    记原图为$G$, 构造的新图为$G^{\prime }$,可以证明通过如下的构造方式得到的$G^{\prime }$和原图一一对应：     构造新源点S和新汇点T。对于每个点，计算其A[i] = 入边权值和-出边权值和（这里的入边和出边都指的是下界）。如果对于当前点的 A[i] = 入边权值和-出边权值和 > 0, 那么源点S向i点连一条权值为A[i]的边；如果A[i]<0,那么i点向汇点T连一条权值为-A[i]的边。对于原图$G$中的其他边，其上界为c，下界为d，那么在$G^{\prime }$中对应的边为d-c。将题目给定的源点t和汇点s连一条权值为无穷的边，保证流量守恒。从s到t的最大流等于 从新源点S到新汇点T的最大流中s->t的流+去除t到s的边后以s和t为源汇点的最大流。     只有当S向每个i点连的边全部跑满时$G$和$G^{\prime }$才会一一对应，也就是说只有跑满时才会有答案。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jU2opeUA-1601723735412)(https://i.loli.net/2020/09/24/iN1HBAXhp7x8Iwk.jpg)]

1.2.2.3 有源汇上下界最小流

    记原图为$G$, 构造的新图为$G^{\prime }$,可以证明通过如下的构造方式得到的$G^{\prime }$和原图一一对应：     构造新源点S和新汇点T。对于每个点，计算其A[i] = 入边权值和-出边权值和（这里的入边和出边都指的是下界）。如果对于当前点的 A[i] = 入边权值和-出边权值和 > 0, 那么源点S向i点连一条权值为A[i]的边；如果A[i]<0,那么i点向汇点T连一条权值为-A[i]的边。对于原图$G$中的其他边，其上界为c，下界为d，那么在$G^{\prime }$中对应的边为d-c。将题目给定的源点t和汇点s连一条权值为无穷的边，保证流量守恒。从s到t的最大流等于 从新源点S到新汇点T的最大流中s->t的流 - 去除t到s的边后以t和s为源汇点的最大流。     只有当S向每个i点连的边全部跑满时$G$和$G^{\prime }$才会一一对应，也就是说只有跑满时才会有答案。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TbtpXUn5-1601723735415)(https://i.loli.net/2020/09/24/KS2kPE9zwp8ytHM.jpg)]

1.2.3 最大流之多源汇最大流

添加一个虚拟源点和虚拟汇点，然后跑dinic算法

1.2.4 最大流之关键边

关键边为： 增加这条边的容量后，整个图的最大流能够变大。 关键边的判定为： u->v这条边满流，且S->v不满流，v->T也不满流。因此跑完dinic后，只需要遍历每一条边，判断是否能够通过不满流的方式到达u和v即可，这个过程可以通过分别从s和t进行dfs即可。

1.2.5 拆点

如果一个点被使用的次数上限固定，那么需要将这个点拆分为两个点，这两个点间连一条边，权值为使用的次数上限 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7VeyFos8-1601723735416)(https://i.loli.net/2020/09/24/8OycAtGxvaPN7jI.jpg)]

1.3 最小割

问题描述 割其实就是删边的意思，当然最小割就是割掉 $X$ 条边来让 $S$ 跟 $T$ 不互通。我们要求 $X$ 条边加起来的流量综合最小。这就是最小割问题。 最大流最小割定理 以下3个条件互相等价：

可行流$f$是最大流其对应的残量网络中不存在增广路存在某个割$cut(S,T),f=cut(S,T)$

1.3.1 最大闭合权子图

定义 有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。 如下图： 能选的子图有Ø,{4},{3,4},{2,4},{1,2,3,4},它们的权值分别为0,-1,5,-6,4. 所以最大权闭合子图为{3,4}，权值为5. 方法 从源点s向每个正权点连一条容量为权值的边，每个负权点向汇点t连一条容量为权值的绝对值的边，有向图原来的边容量全部为无限大。 最大权闭合子图的权值 = 闭合子图内所有权值为正数的点权和-最小割

1.3.2 最大密度子图

定义一个无向图$G=(V,E)$的密度$D=\frac{|E|}{|V|}$ 给出一个无向图$G=(V,E)$，其具有最大密度子图$G^{\prime }=(V,E)$称为最大密度子图，即最大化$D^{\prime }=\frac{|E^{\prime }|}{|V^{\prime }|}$

建图： 设一个极大值U,对于每个点i，S向i连一条边，权值为U;每个i向T连一条边，权值为2*g-di+U (g表示子图的密度，U为极大值,di为i点的度)；对于原图的边i->j，连接一条i->j的边，权值为原图的权值。 如下图所示： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ddyIqqVY-1601723735420)(https://i.loli.net/2020/09/27/AFropO2bLdEYZKN.jpg)] 一般处理思路为： 二分密度g，然后建图判断去找到g值。 对于打印最大密度子图的问题，只需要从S点dfs，将有流量的点放入集合U。U-{S}记为答案。

1.3.3 最小权覆盖集

在一张二分图内选择k个点，使得图中任意一条边至少有一个点被选中。如果这个点集的权值和最小，那么就是一个最小权覆盖集。这个模型针对每个点的权值都是正值的情况。 建图： 1、先对图二分染色，对于每条边两端点的颜色不同 2、然后建立源点S，向其中一种颜色的点连一条容量为该点权值的边 3、建立汇点T，由另一种颜色的点向T连一条容量为该点权值的边 4、对于二分图中原有的边，改为由与S相连的点连向与T相连的点的一条容量为INF的边 跑一遍最小割（最大流），其结果就是最小点权和。

1.3.4 最大权独立集

在一张二分图选择k个点，使得k个点间没有相互连接的边，同时使得这k个点的权值和最大。这个模型针对每个点的权值都是正值的情况。 结论： 最大权独立集 = 所有点的权值和 - 最小点覆盖集

1.4 费用流

给定一个网络 $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)$ 。 费用 我们定义一条边的费用 $w(u,v)$ 表示边 $(u,v)$ 上单位流量的费用。也就是说，当边 (u,v) 的流量为 $f(u,v)$ 时，需要花费 $f(u,v)\times w(u,v)$ 的费用。 最小费用最大流 网络流图中，花费最小的最大流被称为 最小费用最大流 ，这也是接下来我们要研究的对象。

2. 板子

2.1 最大流

2.1.1 最大流算法

2.1.1.1 EK算法

O(nm²)，实际操作中点数$10^3\sim 10^4$

#include <bits/stdc++.h> using namespace std; int const N = 1e3 + 10, M = 1e4 + 10, INF = 1e9 + 10; int e[M * 2], ne[M * 2], f[M * 2], idx, h[N]; int d[N], st[N], n, m, S, T, pre[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++; } // bfs找增广路 int bfs() { memset(st, 0, sizeof st); queue<int> q; q.push(S); st[S] = 1; d[S] = INF; while (q.size()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i]){ int j = e[i]; if (st[j] || !f[i]) continue; // 走过或者没有流 st[j] = 1; d[j] = min(d[t], f[i]); // d记做到达T的可增广流 pre[j] = i; // pre记录到达j点的边为i if (j == T) return d[T]; q.push(j); } } return 0; } int EK() { int res = 0; while (bfs()) { // 如果能够找到增广路 res += 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 res; } int main() { cin >> n >> m >> S >> T; memset(h, -1, sizeof h); for (int i = 1, a, b, c; i <= m; ++i) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); // 建立正向边和反向边 } printf("%d\n", EK()); return 0; }

2.1.1.2 dinic算法

O(n²m)，实际操作中点数$10^4\sim 10^5$

#include <bits/stdc++.h> using namespace std; int const N = 1e4 + 10, M = 1e5 + 10, INF = 1e9 + 10; int e[M * 2], ne[M * 2], h[N], f[M * 2], idx; int d[N], cur[N], n, m, S, T; 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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { memset(h, -1, sizeof h); cin >> n >> m >> S >> T; for (int i = 1, a , b, c; i <= m; ++i) { // 建图 scanf("%d%d%d", &a, &b, &c); add(a, b, c); } printf("%d\n", dinic()); return 0; }

2.1.2 上下界可行流

2.1.2.1 无源汇上下界可行流

#include <bits/stdc++.h> using namespace std; const int N = 210, M = (10200 + N) * 2, INF = 1e8; int e[M], ne[M], h[N], idx, f[M], A[N], l[M]; int d[N], cur[N], n, m, S, T; void add(int a, int b, int c, int d) { e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx++; e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++; } int bfs() { queue<int> q; q.push(S); memset(d, -1, sizeof d); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { memset(h, -1, sizeof h); int tot = 0; // 记录S流出的流量 cin >> n >> m; S = 0, T = n + 1; for (int i = 1, a, b, c, d; i <= m; ++i) { scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, c, d); A[a] -= c, A[b] += c; // 计算A[i]，流入-流出 } for (int i = 1; i <= n; ++i) { if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i]; // A[i] > 0, 从S引到i else if (A[i] < 0) add(i, T, 0, -A[i]); // A[i] < 0, 从i引到T } if (dinic() != tot) printf("NO\n"); // 流量没有跑满，无解 else { printf("YES\n"); for (int i = 0; i < m * 2; i += 2) { printf("%d\n", l[i] + f[i ^ 1]); // 最小值+残量网络中反向边的值(因为跑满后正向边为0.反向边为流量) } } return 0; }

2.1.2.2 有源汇上下界最大流

#include <bits/stdc++.h> using namespace std; int const N = 212, M = (N + 10010) * 2, INF = 1e9 + 10; int e[M], ne[M], f[M], idx, h[N]; int d[N], cur[N], n, m, S, T, A[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 bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(S); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if(d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while(bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { int s, t; memset(h, -1, sizeof h); int tot = 0; cin >> n >> m >> s >> t; S = 0, T = n + 1; for (int i = 1, a, b, c, d; i <= m; ++i) { scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, d - c); A[a] -= c, A[b] += c; // 计算 入流-出流 } for (int i = 1; i <= n; ++i) { if (A[i] > 0) add(S, i, A[i]), tot += A[i]; // 入流大于0，建S->i else if (A[i] < 0) add(i, T, -A[i]); // 出流大于0，建i->T } add(t, s, INF); // 补充t->s，为了保证在S、T为源汇点的图中流量守恒 if (dinic() < tot) printf("No Solution\n"); // 无解情况 else { int res = f[idx - 1]; // S、T为源汇点时s、t的流量 S = s, T = t; // 改变源汇点 f[idx - 1] = f[idx - 2] = 0; // 删除t->s那条边 printf("%d\n", res + dinic()); // 答案累加上 s、t为源汇点时的最大流 } return 0; }

2.1.2.3 有源汇上下界最小流

#include <bits/stdc++.h> using namespace std; const int N = 50010, M = (N + 125003) * 2, INF = 2147483647; int e[M], ne[M], f[M], idx, h[N]; int d[N], cur[N], n, m, S, T, A[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 bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(S); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if(d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while(bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { int s, t; memset(h, -1, sizeof h); int tot = 0; cin >> n >> m >> s >> t; S = 0, T = n + 1; for (int i = 1, a, b, c, d; i <= m; ++i) { scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, d - c); A[a] -= c, A[b] += c; // 计算 入流-出流 } for (int i = 1; i <= n; ++i) { if (A[i] > 0) add(S, i, A[i]), tot += A[i]; // 入流大于0，建S->i else if (A[i] < 0) add(i, T, -A[i]); // 出流大于0，建i->T } add(t, s, INF); // 补充t->s，为了保证在S、T为源汇点的图中流量守恒 if (dinic() < tot) printf("No Solution\n"); // 无解情况 else { int res = f[idx - 1]; // S、T为源汇点时s、t的流量 S = t, T = s; // 改变源汇点 f[idx - 1] = f[idx - 2] = 0; // 删除t->s那条边 printf("%d\n", res - dinic()); // 答案减去上 t、s为源汇点时的最大流 } return 0; }

2.2 最小割

2.2.1 基本概念

最小割=最大流，因此求最小割就是求最大流，板子见最大流

2.2.2 最大权闭合子图

最大权闭合子图的权值 = 闭合子图内所有权值为正数的点权和-最小割

2.2.3 最大密度子图

2.3 费用流

求最小费用流

#include <bits/stdc++.h> using namespace std; int const N = 5010, M = 50010 * 2, INF = 1e9; int e[M], h[M], w[M], idx, ne[M], d[N], incf[N], f[M], pre[N], st[N]; // d[i]到达i点的最小花费和，incf[i]到达i点的最大流 int n, m, S, T; 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++; } // spfa找到最小花费的增广路 int spfa() { memset(d, 0x3f, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] <= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } void EK(int& flow, int& cost) { flow = cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } } int main() { memset(h, -1, sizeof h); cin >> n >> m >> S >> T; for (int i = 1, a, b, c, d; i <= m; ++i) { // 读入边 scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, c, d); } int flow, cost; EK(flow, cost); // 类EK算法求最小费用最大流 printf("%d %d\n", flow, cost); return 0; }

如果求最大费用流，有如下两种方法

将费用取负，然后跑最小费用流，求出来的费用再取负即可 // 还原网络，然后将费用取负，再求最小费用流，费用取反就是答案 for (int i = 0; i < idx; i += 2) { f[i] += f[i ^ 1], f[i ^ 1] = 0; w[i] = -w[i], w[i ^ 1] = -w[i ^ 1]; } printf("%d\n", -EK()); 将spfa求最短路改成求最长路，然后使用最长路更新 // spfa找最长路 int spfa() { memset(d, 0xc0, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] >= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; }

2.4 其他操作

2.4.1 还原网络

for (int j = 0; j < idx; j += 2) { // 每次恢复一下原来的网络 f[j] += f[j ^ 1]; f[j ^ 1] = 0; }

2.4.1 打印方案

for (int i = 0; i < idx; i += 2) { if (e[i] > m && e[i] <= n && !f[i]) printf("%d %d\n", e[i ^ 1], e[i]); }

3. 典型例题

3.1 最大流

3.1.1 二分图匹配

acwing2175. 飞行员配对方案问题 题意： 有多么飞行员，其中前1 ~ m名为外籍飞行员，m+1 ~ n为英国飞行员，给出多对外籍飞行员和英国飞行员的配对关系，找出最多能够匹配的数量，并打印出匹配关系 题解： 虚拟出源点和汇点，源点向1 ~ m分别连出一条权值为1的边，m+1向n分别练出一条权值为1的边，然后对于1 ~ m 和 m + 1 ~ n之间的点，权值全部设置为1。跑最大流。对于路径打印，只需要枚举每一条边，然后判断e[i]是否在m+1 ~ n的范围内即可。 代码：

#include <bits/stdc++.h> using namespace std; int const N = 110, M = 5210, INF = 1e9 + 10; int e[M], ne[M], f[M], h[N], idx; int d[N], cur[N], n, m, S, T; 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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { 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(scanf("%d%d", &a, &b) && a != -1) add(a, b, 1); printf("%d\n", dinic()); // 打印方案 for (int i = 0; i < idx; i += 2) { if (e[i] > m && e[i] <= n && !f[i]) printf("%d %d\n", e[i ^ 1], e[i]); } return 0; }

acwing2179. 圆桌问题 题意： 假设有来自 m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri(i=1,2,…,m)。会议餐厅共有 n 张餐桌，每张餐桌可容纳 ci(i=1,2,…,n) 个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。 1≤m≤150,1≤n≤270,1≤ri,ci≤100 题解： 设S = 0，T = n + m + 1, 把每个单位和圆桌都当成一个点，单位为1 ~ m, 圆桌为m + 1 ~ m + n。s向每个单位连一条边，边权为单位人数；每个圆桌向T连一条边，边权为圆桌人数；每个单位向每个圆桌连一条边权为1的边。然后dinic跑最大流。 代码：

#include <bits/stdc++.h> using namespace std; int const N = 150 + 270 + 10, M = N * N, INF = 1e9 + 10; int e[M], ne[M], f[M], h[N], idx; int d[N], cur[N], n, m, S, T; 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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { memset(h, -1, sizeof h); int tot = 0; cin >> m >> n; S = 0, T = n + m + 1; for (int i = 1, c; i <= m; ++i) { scanf("%d", &c); add(S, i, c); tot += c; } for (int i = 1, c; i <= n; ++i) { scanf("%d", &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) printf("0\n"); else { printf("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]) printf("%d ", e[j] - m); } printf("\n"); } } return 0; }

3.1.2 上下界可行流

3.1.2.1 无源汇上下界可行流

acwing2188. 无源汇上下界可行流 题意： 给定一个包含 n 个点 m 条边的有向图，每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。1≤n≤200,1≤m≤10200,1≤a,b≤n,0≤c≤d≤10000 题解： 原来的流假设都为最小流。建一个附加流的残量网络， 然后求残量网络的最大流附加到原来的流上。A[i]表示原来网络i点的流入量-流出量，如果A[i] > 0，则在附加流中需要流出量 - 流入量=A[i],因此流出量更大，需要一个源点S流入这个差值A[i],因此从S流到i点权值为A[i]的边；同理，如果A[i] < 0, 则需要i流向T权值为A[i]的边。最后求出可行流时，是最大流加上原来流的最小值。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 210, M = (10200 + N) * 2, INF = 1e8; int e[M], ne[M], h[N], idx, f[M], A[N], l[M]; int d[N], cur[N], n, m, S, T; void add(int a, int b, int c, int d) { e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx++; e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++; } int bfs() { queue<int> q; q.push(S); memset(d, -1, sizeof d); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { memset(h, -1, sizeof h); int tot = 0; // 记录S流出的流量 cin >> n >> m; S = 0, T = n + 1; for (int i = 1, a, b, c, d; i <= m; ++i) { scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, c, d); A[a] -= c, A[b] += c; // 计算A[i]，流入-流出 } for (int i = 1; i <= n; ++i) { if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i]; // A[i] > 0, 从S引到i else if (A[i] < 0) add(i, T, 0, -A[i]); // A[i] < 0, 从i引到T } if (dinic() != tot) printf("NO\n"); // 流量没有跑满，无解 else { printf("YES\n"); for (int i = 0; i < m * 2; i += 2) { printf("%d\n", l[i] + f[i ^ 1]); // 最小值+残量网络中反向边的值(因为跑满后正向边为0.反向边为流量) } } return 0; }

3.1.2.2 有源汇上下界最大流

acwing2189. 有源汇上下界最大流 题意： 给定一个包含 n 个点 m 条边的有向图，每条边都有一个流量下界和流量上界。给定源点 S 和汇点 T，求源点到汇点的最大流。 1≤n≤202,1≤m≤9999,1≤a,b≤n,0≤c≤d≤105 题解： 可以证明： s、t为源汇点的最大流 = S、T为源汇点时s、t的流量+s、t为源汇点时的最大流 代码：

#include <bits/stdc++.h> using namespace std; int const N = 212, M = (N + 10010) * 2, INF = 1e9 + 10; int e[M], ne[M], f[M], idx, h[N]; int d[N], cur[N], n, m, S, T, A[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 bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(S); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if(d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while(bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { int s, t; memset(h, -1, sizeof h); int tot = 0; cin >> n >> m >> s >> t; S = 0, T = n + 1; for (int i = 1, a, b, c, d; i <= m; ++i) { scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, d - c); A[a] -= c, A[b] += c; // 计算 入流-出流 } for (int i = 1; i <= n; ++i) { if (A[i] > 0) add(S, i, A[i]), tot += A[i]; // 入流大于0，建S->i else if (A[i] < 0) add(i, T, -A[i]); // 出流大于0，建i->T } add(t, s, INF); // 补充t->s，为了保证在S、T为源汇点的图中流量守恒 if (dinic() < tot) printf("No Solution\n"); // 无解情况 else { int res = f[idx - 1]; // S、T为源汇点时s、t的流量 S = s, T = t; // 改变源汇点 f[idx - 1] = f[idx - 2] = 0; // 删除t->s那条边 printf("%d\n", res + dinic()); // 答案累加上 s、t为源汇点时的最大流 } return 0; }

3.1.2.3 有源汇上下界最小流

acwing2190. 有源汇上下界最小流 题意： 给定一个包含 n 个点 m 条边的有向图，每条边都有一个流量下界和流量上界。给定源点 S 和汇点 T，求源点到汇点的最小流。 题解： 可以证明： s、t为源汇点的最小流 = S、T为源汇点时s、t的流量-t、s为源汇点时的最大流 代码：

#include <bits/stdc++.h> using namespace std; const int N = 50010, M = (N + 125003) * 2, INF = 2147483647; int e[M], ne[M], f[M], idx, h[N]; int d[N], cur[N], n, m, S, T, A[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 bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(S); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if(d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while(bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { int s, t; memset(h, -1, sizeof h); int tot = 0; cin >> n >> m >> s >> t; S = 0, T = n + 1; for (int i = 1, a, b, c, d; i <= m; ++i) { scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, d - c); A[a] -= c, A[b] += c; // 计算 入流-出流 } for (int i = 1; i <= n; ++i) { if (A[i] > 0) add(S, i, A[i]), tot += A[i]; // 入流大于0，建S->i else if (A[i] < 0) add(i, T, -A[i]); // 出流大于0，建i->T } add(t, s, INF); // 补充t->s，为了保证在S、T为源汇点的图中流量守恒 if (dinic() < tot) printf("No Solution\n"); // 无解情况 else { int res = f[idx - 1]; // S、T为源汇点时s、t的流量 S = t, T = s; // 改变源汇点 f[idx - 1] = f[idx - 2] = 0; // 删除t->s那条边 printf("%d\n", res - dinic()); // 答案减去上 t、s为源汇点时的最大流 } return 0; }

3.1.3 多源汇最大流

acwing2234. 多源汇最大流 题意： 给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量，边的容量非负。其中有 Sc 个源点，Tc 个汇点。图中可能存在重边和自环。求整个网络的最大流。2≤n≤10000,1≤m≤10⁵,0≤c≤10000, 题解： 添加一个虚拟源点和虚拟汇点，然后跑dinic算法 代码：

#include <bits/stdc++.h> using namespace std; int const N = 10010, M = (N + 100010) * 2, INF = 1e9 + 10; int e[M], ne[M], h[N], f[M], idx; int cur[N], d[N], n, m, S, T, sc, st; 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 bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for(int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } return flow; } int dinic() { int res = 0, flow = 0; while(bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { cin >> n >> m >> sc >> st; memset(h, -1, sizeof h); T = 0, S = n + 1; for (int i = 1, t; i <= sc; ++i) { scanf("%d", &t); add(S, t, INF); // 虚拟源点S->si连边 } for (int i = 1, t; i <= st; ++i) { scanf("%d", &t); add(t, T, INF); // ti->虚拟汇点S } for (int i = 1, a, b, c; i <= m; ++i) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); } printf("%d\n", dinic()); return 0; }

3.1.4 关键边

acwing2236. 伊基的故事 I - 道路重建 题意： 给定N个点M条边，N个点从0~N-1,S为0，t 为N-1，找出关键边。关键边为：增加这条边的容量后，整个图的最大流能够变大。1≤N≤500,1≤M≤5000,0≤a,b<N,0≤c≤100 题解： 关键边的判定为： u->v这条边满流，且S->v不满流，v->T也不满流。因此跑完dinic后，只需要遍历每一条边，判断是否能够通过不满流的方式到达u和v即可。 代码：

#include <bits/stdc++.h> using namespace std; int const N = 510, M = (N + 5010) * 2, INF = 1e9 + 10; int e[M], ne[M], h[N], f[M], idx; int d[N], cur[N], n, m, S, T, vis_t[N], vis_s[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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } // 判断st数组是否可达 void dfs(int u, int st[], int t) { st[u] = 1; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i], edge = i ^ t; if (f[edge] && !st[j]) dfs(j, st, t); } } int main() { memset(h, -1, sizeof h); cin >> n >> m; S = 0, T = n - 1; for (int i = 1, a, b, c; i <= m; ++i) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); } dinic(); dfs(S, vis_s, 0); // 判断从S出发是否可达 dfs(T, vis_t, 1); // 判断从T出发是否可达 int res = 0; for (int i = 0; i < m * 2; i += 2) { // 遍历每一条边 if (!f[i] && vis_s[e[i ^ 1]] && vis_t[e[i]]) res++; // 如果这条边的残量为0，且u和v都可达，答案++ } cout << res << endl; return 0; }

3.1.5 最大流判定

acwing2277. 秘密挤奶机 题意： 农场由 N 个点（编号 1∼N）， P 条双向道路（编号 1∼P）组成。每条道路的长度为正，且不超过 10⁶。多条道路可能连接同一对地标。农场中的任何一条道路都最多只能使用一次，并且他应该尝试使用尽可能短的道路。帮助约翰从牛棚（地标 1）到达秘密挤奶机（地标 N）总共 T 次。找到他必须使用的最长的单个道路的最小可能长度。 题解： 要在网络中，找最大值的最小值，二分答案。为了保证每条边只被走一次，可以让小于二分答案mid的为1，大于二分答案的为0。然后跑最大流判断和K的关系。如果大于等于K，说明答案太大；反之，答案太小。 代码：

#include <bits/stdc++.h> using namespace std; int const N = 210, M = (N + 40010) * 2, INF = 1e9 + 10; int e[M], ne[M], h[N], idx, f[M], w[M]; int d[N], cur[N], n, m, S, T, K; void add(int a, int b, int c) { // 这是建立无向边，等价于两条有向边的叠加，然后反边也叠加起来，这样4条边变为2条边 e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } bool check(int mid) { for (int i = 0; i < idx; i ++) { if (w[i] > mid) f[i] = 0; else f[i] = 1; } return dinic() >= K; } int main() { cin >> n >> m >> K; memset(h, -1, sizeof h); S = 1, T = n; for (int i = 1, a, b, c; i <= m; ++i) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); } // 二分枚举答案 int l = 1, r = 1000000; while(l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // 如果能够找到大于等于K的流，说明答案太大 else l = mid + 1; } printf("%d\n", l); return 0; }

acwing2187. 星际转移问题 题意： 现有 n 个太空站（编号 1∼n）位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 H[i] 个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4) 表示该太空船将周期性地停靠太空站 134134134…。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上，太空船全在初始站，即行驶周期中的第一个站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。1≤n≤13,1≤m≤20,1≤k≤50,1≤r≤n+2, 题解： 把每个空间站拆分称为n+2个点，每个点表示为<位置，天数>，空间船的前一个站向后一个站连一条边，权值为空间船的载重量；同一个位置的前一天向后一天连一条正无穷的边，表示人可以在原地不动；源点(地球)向<0, 0>连一条权值为k的边，表示最开始只能由这里走k个人；每个<n+1, i>向T(月球)连一条权值为正无穷的边，表示当人走到n+1的位置时就是在月球。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 1101 * 22 + 10, M = (N + 1100 + 13 * 1101) + 10, INF = 1e8; int n, m, k, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; struct Ship { int h, r, id[30]; }ships[30]; int p[30]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int get(int i, int day) { return day * (n + 2) + i; } 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 bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } int main() { scanf("%d%d%d", &n, &m, &k); S = N - 2, T = N - 1; // 地球和月球 memset(h, -1, sizeof h); for (int i = 0; i < 30; i ++ ) p[i] = i; // 初始化并查集，使用并查集来判断是否可达 for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); ships[i] = {a, b}; for (int j = 0; j < b; j ++ ) { int id; scanf("%d", &id); if (id == -1) id = n + 1; ships[i].id[j] = id; // 记录每辆车的路径数目 if (j) { int x = ships[i].id[j - 1]; p[find(x)] = find(id); // 可达的店连接起来 } } } if (find(0) != find(n + 1)) puts("0"); // 如果不可达 else { add(S, get(0, 0), k); // 源点向初始点连一条边 add(get(n + 1, 0), T, INF); // 到达n+1点，这时向T连边 int day = 1, res = 0; while (true) { add(get(n + 1, day), T, INF); // n+1天表示到达月球，连边 for (int i = 0; i <= n + 1; i ++ ) add(get(i, day - 1), get(i, day), INF); // 人可以在原地不动 for (int i = 0; i < m; i ++ ) { int r = ships[i].r; int a = ships[i].id[(day - 1) % r], b = ships[i].id[day % r]; add(get(a, day - 1), get(b, day), ships[i].h); // 车的前一个站向后一个站连边 } res += dinic(); // 每次增加一个点然后增广 if (res >= k) break; // 大于等于k，能够把k人都送到月球，break day ++ ; } printf("%d\n", day); } return 0; }

3.1.6 拆点

acwing2240. 餐饮 题意： 每头奶牛都有自己喜欢的食物和饮料，并且不会食用其他不喜欢的食物和饮料。农夫约翰一共烹制了 F 种食物，并提供了 D 种饮料。约翰共有 N 头奶牛，其中第 i 头奶牛有 Fi 种喜欢的食物以及 Di 种喜欢的饮料。约翰需要给每头奶牛分配一种食物和一种饮料，并使得有吃有喝的奶牛数量尽可能大。每种食物或饮料都只有一份，所以只能分配给一头奶牛食用（即，一旦将第 2 种食物分配给了一头奶牛，就不能再分配给其他奶牛了）。1≤N,F,D≤100,1≤Fi≤F,1≤Di≤D 题解： 奶牛拆成奶牛1和奶牛2两种点，然后中间连一条权值为1的边；S->饮料，权值为1；饮料->奶牛1，权值为1；奶牛1->奶牛2，权值为1；奶牛2->食品，权值为1；食品->T,权值为1。然后跑dinic 代码：

#include <bits/stdc++.h> using namespace std; const int N = 410, M = 40610, INF = 1e8; int n, F, D, S, T; int h[N], e[M], f[M], ne[M], idx; int 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 ++ ; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { scanf("%d%d%d", &n, &F, &D); S = 0, T = n * 2 + F + D + 1; memset(h, -1, sizeof h); for (int i = 1; i <= F; i ++ ) add(S, n * 2 + i, 1); // S->食品 for (int i = 1; i <= D; i ++ ) add(n * 2 + F + i, T, 1); // 饮料->T for (int i = 1; i <= n; i ++ ) { add(i, n + i, 1); // 奶牛1->奶牛2 int a, b, t; scanf("%d%d", &a, &b); while (a -- ) { scanf("%d", &t); add(n * 2 + t, i, 1); // 食品->奶牛1 } while (b -- ) { scanf("%d", &t); add(i + n, n * 2 + F + t, 1); // 奶牛2->饮料 } } printf("%d\n", dinic()); return 0; }

acwing2180. 最长递增子序列问题 题意： 给定正整数序列 $x_1,\cdots ,x_n。$

计算其最长递增子序列的长度 s。计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。（给定序列中的每个元素最多只能被取出使用一次）如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$，则从给定序列中最多可取出多少个长度为 s 的递增子序列。

注意:递增指非严格递增。 1≤n≤500

题解： 第一问求最长上升子序列可以使用dp出来 第二问建图如下： 每个点a[i]拆分为a[i]和a[i+n],从a[i]->a[i+1]连一条权值为1的边，从S向每个上升子序列的起点连一条权值为1的边，每个上升子序列内部连边，权值为1，从每个长度为s的子序列的尾部连一条权值为1的边到T，然后dinic即可 第三问： 改变S->a[1]的边权值为正无穷，a[1]->a[1+n]的边权值为正无穷；改变a[n]->a[n+n]的边权值为正无穷，a[n+n]->T的边权值为正无穷。 第二问建图如下，第三问修改的边权用红色标出 同时，网络流如果增大边权不需要重新建图，直接修改完后进行增广即可 这种区间覆盖问题都可以使用网络流处理，适用于点数较小的情况 代码：

#include <bits/stdc++.h> using namespace std; const int N = 1010, M = 251010, INF = 1e8; int n, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; int g[N], w[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 ++ ; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } int main() { scanf("%d", &n); S = 0, T = n * 2 + 1; memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); int s = 0; for (int i = 1; i <= n; i ++ ) { add(i, i + n, 1); g[i] = 1; for (int j = 1; j < i; j ++ ) if (w[j] <= w[i]) g[i] = max(g[i], g[j] + 1); for (int j = 1; j < i; j ++ ) if (w[j] <= w[i] && g[j] + 1 == g[i]) add(n + j, i, 1); // j->i是上升子序列，j+n->i连边权值为1 s = max(s, g[i]); if (g[i] == 1) add(S, i, 1); // S向每个上升子序列的起点连边，权值为1 } for (int i = 1; i <= n; i ++ ) if (g[i] == s) add(n + i, T, 1); // 每个长度为s的子序列终点向T连边 printf("%d\n", s); if (s == 1) printf("%d\n%d\n", n, n); // 如果长度为1，那么需要特判 else { int res = dinic(); // 先跑网络流 printf("%d\n", res); for (int i = 0; i < idx; i += 2) {// 修改S->1，1->1+n，n->n+n,n+n->T的权值为正无穷 int a = e[i ^ 1], b = e[i]; if (a == S && b == 1) f[i] = INF; else if (a == 1 && b == n + 1) f[i] = INF; else if (a == n && b == n + n) f[i] = INF; else if (a == n + n && b == T) f[i] = INF; } printf("%d\n", res + dinic()); // 再做一次增广，累加到上一次的答案上 } return 0; }

acwing2278. 企鹅游行 题意： 作为群居动物，企鹅们喜欢聚在一起，因此，它们想在同一块浮冰上会合。企鹅们利用自己有限的跳跃能力，在一块块浮冰之间跳跃移动，从而聚在一起。起跳的浮冰会遭到破坏，每块浮冰可以允许起跳的次数已知，落点的浮冰并不会因此受到影响。当浮冰被破坏到一定程度时，浮冰就会消失。请帮助企鹅找出它们可以会合的所有浮冰。$1\le T\le 100,1\le N\le 100,0\le D\le 105,-10000\le xi,yi\le 10000,0\le ni\le 10,1\le mi\le 200$ 题解： 建图如下： 设置虚拟源点S，虚拟源点S向每个一开始有企鹅的浮冰连一条边，权值为该浮冰上的企鹅数目。每个浮冰拆分为两个点i和i+n，i->i+n连边，权值为浮冰起跳承载数。每个可以互相跳到的浮冰i和j，i+n->j连一条边，权值为正无穷。如下图： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iGSxvDF9-1601723735426)(https://i.loli.net/2020/09/25/sgZanuOwR4rMT8m.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; int const N = 210, M = 3e4 + 10, INF = 1e8; double eps = 1e-8; int kases, n, S, T; double limit; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; struct PO{ int x, y; }po[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 ++ ; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { int t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } bool check(PO a, PO b ) { double dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy < limit * limit + eps; } int main() { cin >> kases; while(kases--) { S = 0; int tot = 0; memset(h, -1, sizeof h); idx= 0; cin >> n >> limit; for (int i = 1; i <= n; ++i) { int x, y, cnt, weight; cin >> x >> y >> cnt >> weight; po[i].x = x, po[i].y = y; add(i, i + n, weight); // 把冰块拆分为2个，连一条边，权值为冰块的载重量 tot += cnt; // 计算企鹅的数目 add(S, i, cnt); // 源点向冰块连一条边，权值为企鹅个数 } // 把能够跳到的冰块互相连边 for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { if (check(po[i], po[j])) { add(i + n, j, INF); add(j + n, i, INF); } } } int flg = -1; // 判断是否找到解 for (int i = 1; i <= n; ++i) { T = i; for (int j = 0; j < idx; j += 2) { // 每次恢复一下原来的网络 f[j] += f[j ^ 1]; f[j ^ 1] = 0; } int res = dinic(); if (res == tot) { // 如果找到解 flg = 0; cout << i - 1 << " "; } } if (flg == -1) cout << -1; cout << endl; } return 0; }

3.1.7 特殊建图

acwing2237. 猪 题意： 米尔克在一家养猪场工作，该养猪场共有 M 个上了锁的猪舍。由于米尔克没有钥匙，所以他无法打开任何猪舍。顾客们顺次来到了养猪场，不会有两个顾客同一时间过来。他们中的每个人都有一些猪舍的钥匙，并且想买一定数量的猪。米尔克每天一大早就可以得到计划在当天来到农场的客户的所有数据，以便他制定销售计划，从而最大限度地提高出售生猪的数量。 更准确的说，过程如下：

顾客到达养猪场，将所有他有钥匙的猪舍的大门全部打开，米尔克从所有未上锁的猪舍中挑选一定数量的猪卖给该顾客。如果米尔克愿意，他还可以给未上锁的猪舍里剩下的猪重新分配位置。 在每个顾客到达之前，会将上一个顾客打开的猪舍全部关闭。每个猪舍中都可以放置无限数量的猪。

请你编写一个程序，计算他当天可以出售的生猪的最大数量。$1\le M\le 1000,1\le N\le 100,0\le A\le M,1\le Ki\le M,0\le B\le 10000$ 题解： 顾客可以将被打开的猪舍内的猪重新分配，相当于顾客拥有了所有的猪，然后再分配，为了保证顾客间的时序关系，删除猪的点，只留下顾客的点。建图：虚拟源点S向每个第一次打开猪舍的顾客连边，权值为该猪舍内猪的数目；每个顾客向后一个打开相同猪舍的顾客连边，权值为正无穷；每个顾客向汇点连边，权值为买的猪数目，如下图： 代码:

#include <bits/stdc++.h> using namespace std; const int N = 110, M = 100200 * 2 + 10, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; int w[1010], belong[1010]; 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 bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { int t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } int main() { scanf("%d%d", &m, &n); S = 0, T = n + 1; // 虚拟源汇点 memset(h, -1, sizeof h); for (int i = 1; i <= m; i ++ ) scanf("%d", &w[i]); // 读入每个猪蛇内猪的数目 for (int i = 1; i <= n; i ++ ) { int a, b; scanf("%d", &a); // 读入顾客有的猪舍钥匙数目 while (a -- ) { int t; scanf("%d", &t); if (!belong[t]) add(S, i, w[t]); // 如果第一次打开，源点->猪舍，权值为猪舍内猪数目 else add(belong[t], i, INF); // 不是第一次被打开，那么上一个顾客向当前顾客连边，权值为正无穷 belong[t] = i; } scanf("%d", &b); add(i, T, b); // 每个顾客向汇点连边，权值为买的猪的数目 } printf("%d\n", dinic()); return 0; }

3.2 最小割

3.2.1 直接应用

AcWing 2279. 网络战争 题意： 给出一个带权无向图 G=(V,E)，每条边 e 有一个权 we。求将点 s 和点 t 分开的一个边割集 C，使得该割集的平均边权最小，即最小化： $\frac{w(e)}{|c|}$ 注意： 边割集的定义与最小割中的割边的集合不同。在本题中，一个边割集是指：将这些变删去之后，s 与 t 不再连通。 2≤n≤100, 1≤m≤400, 1≤w≤107, 保证 s 和 t 之间连通。 题解： 考虑分数规划。存在一个平均值不大于x的割集等价于： $\frac{w(e)}{|c|}<=x$ => ${\sum }_{}w(e)-x<=0$ 浮点数二分处理时边从w变为w-e，然后跑最小割，判断是否存在，如果最小割小于0，说明x太大。注意这里的割定义与传统的割定义不一样，如果一条新边的权值小于0，那么必然在最小割里，同时这条新边的权值需要设置为0(网络流的边权要大于等于0) 代码：

#include <bits/stdc++.h> using namespace std; const int N = 110, M = 810, INF = 1e8; const double eps = 1e-8; int n, m, S, T; int h[N], e[M], w[M], ne[M], idx; double f[M]; int d[N], cur[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++ ; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } double find(int u, double limit) { if (u == T) 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 < eps) d[ver] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } } return flow; } double dinic(double mid) { double res = 0; for (int i = 0; i < idx; i += 2) if (w[i] <= mid) { // 如果这条边是负权边，那么直接加入到答案内 res += w[i] - mid; f[i] = f[i ^ 1] = 0; } else f[i] = f[i ^ 1] = w[i] - mid; // 否则，改变边权 double r = 0, flow; while (bfs()) while (flow = find(S, INF)) r += flow; return r + res; } int main() { scanf("%d%d%d%d", &n, &m, &S, &T); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } double l = 0, r = 1e7; while (r - l > eps) { double mid = (l + r) / 2; // 把边权变为w-mid if (dinic(mid) < 0) r = mid; // 最小割小于0，说明mid太大 else l = mid; } printf("%.2lf\n", r); return 0; }

acwing2280. 最优标号 题意： 给定一个无向图 G=(V,E)，每个顶点都有一个标号，它是一个 $[0,2^{31}-1]$ 内的整数。不同的顶点可能会有相同的标号。对每条边 (u,v)，我们定义其费用 cost(u,v) 为 u 的标号与 v 的标号的异或值。现在我们知道一些顶点的标号。你需要确定余下顶点的标号使得所有边的费用和尽可能小。 题解： 由于二进制的每一位都是相互独立的，因此如果能够求得每一位的最小值，那么累加起来也是最小值。因此，对于每一位的最小值，不是0就是1，那么建立二部图，左部为0，右部为1，对于两个点，如果这两个点间有边，那么连接一条容量为1的边，表示最大允许流量为1；如果某个点有标号，如果该位为1，那么该点向T连边，权值为正无穷；如果该位为0，那么S点向该点连边，权值为正无穷。然后求得最小割，累加即可。 代码：

#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 510, M = (3000 + N * 2) * 2, INF = 1e8; int n, m, k, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; int p[N]; PII edges[3010]; void add(int a, int b, int c1, int c2) { e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx ++ ; e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx ++ ; } void build(int k) { memset(h, -1, sizeof h); idx = 0; for (int i = 0; i < m; i ++ ) { int a = edges[i].x, b = edges[i].y; add(a, b, 1, 1); // 每个点添加两条边，正向和反向，权值为1，表示可以流过1的流量，允许一个在0一个在1 } for (int i = 1; i <= n; i ++ ) if (p[i] >= 0) { // 如果有标号 if (p[i] >> k & 1) add(i, T, INF, 0); // 1则在右部图 else add(S, i, INF, 0); // 0则在左部图 } } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } LL dinic(int k) { build(k); // 对于每一位重新建图，然后求最小割 int r = 0, flow; while (bfs()) while (flow = find(S, INF)) r += flow; return r; } int main() { scanf("%d%d", &n, &m); S = 0, T = n + 1; for (int i = 0; i < m; i ++ ) scanf("%d%d", &edges[i].x, &edges[i].y); // 读入每一条边 scanf("%d", &k); memset(p, -1, sizeof p); // 给每个点一个标号 while (k -- ) { int a, b; scanf("%d%d", &a, &b); p[a] = b; } LL res = 0; for (int i = 0; i <= 30; i ++ ) res += dinic(i) << i; // 每个位单独做dinic，然后累加就是答案 printf("%lld\n", res); return 0; }

acwing381. 有线电视网络 题意： 给定一张n个点m条边的无向图，求最少去掉多少个点，可以使图不连通。如果不管去掉多少个点，都无法使原图不连通，则直接返回n。0≤n≤50 题解： 由于要删点，而网络流处理的是删边的问题，因此把每个点拆分为两个点，a出和a入，然后a出->a入。对于每条边，a–b,那么从a出->b入，从b出->a入。然后枚举S和T，最好跑最小割。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xnvMzy0z-1601723735430)(https://i.loli.net/2020/09/28/saKUG1fcHlBEeSF.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; const int N = 110, M = 5210, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], ne[M], idx; int 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 bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { int t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } int main() { while (cin >> n >> m) { memset(h, -1, sizeof h); idx = 0; for (int i = 0; i < n; i ++ ) add(i, n + i, 1); // 每个点拆分为两个点，从a出到b入 while (m -- ) { int a, b; scanf(" (%d,%d)", &a, &b); // a--b有边 add(n + a, b, INF); // a出->b入 add(n + b, a, INF); // b出->a入 } int res = n; for (int i = 0; i < n; i ++ ) for (int j = 0; j < i; j ++ ) { S = n + i, T = j; // 枚举S和T for (int k = 0; k < idx; k += 2) { // 还原网络 f[k] += f[k ^ 1]; f[k ^ 1] = 0; } res = min(res, dinic()); } printf("%d\n", res); } return 0; }

3.2.2 最大权闭合图

acwing961. 最大获利 题意： 新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需 要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i 个通讯中转站需要的成本为 Pi（1≤i≤N） 。另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为 Ai,Bi 和 Ci：这些用户会使用中转站 Ai 和中转站 Bi 进行通讯，公司可以获益 Ci。（1≤i≤M,1≤Ai,Bi≤N）THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和） 题解： 可以把建站的成本看作负数点，每个用户群体当成一个点。每个信号站都为负数，因此将该点向T连边，权值为建站成本；获利为正权点，因此S向该点连边，权值为获利；然后每个点向信号站连边，权值为正无穷。那么建图如下： 可以很明显看出这是一个最大权闭合图问题，按照固定方法建图即可。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 55010, M = (50000 * 3 + 5000) * 2 + 10, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], ne[M], idx; int 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 bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { int t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } int main() { scanf("%d%d", &n, &m); S = 0, T = n + m + 1; memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) { int p; scanf("%d", &p); add(m + i, T, p); // 每个信号站都为负数，因此将该点向T连边，权值为建站成本 } int tot = 0; for (int i = 1; i <= m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(S, i, c); // 获利为正权点，因此S向该点连边，权值为获利 add(i, m + a, INF); // 然后每个点向信号站连边，权值为正无穷 add(i, m + b, INF); tot += c; } printf("%d\n", tot - dinic()); return 0; }

acwing2176. 太空飞行计划问题 题意： W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1,E2,…,Em} 和进行这些实验需要使用的全部仪器的集合 I={I1,I2,…,In}。实验 Ej 需要用到的仪器是 I 的子集 Rj⊆I。配置仪器 Ik 的费用为 ck 美元。实验 Ej 的赞助商已同意为该实验结果支付 pj 美元。W 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。 题解： 每个实验向对应的仪器连有向边，实验的权值为正权值，仪器的权值为负权值，那么就是找到一个最大权闭合子图，按照套路建图即可。然后对于求方案数，只需要dfs一遍，找到S集合，然后判断实验和对应的仪器是否在S集合即可 代码：

#include <bits/stdc++.h> using namespace std; const int N = 110, M = 5210, INF = 1e8; int m, n, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[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 ++ ; } int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { int t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } 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; } void dfs(int u) { st[u] = true; for (int i = h[u]; ~i; i = ne[i]) if (!st[e[i]] && f[i]) dfs(e[i]); } int main() { scanf("%d%d", &m, &n); S = 0, T = m + n + 1; memset(h, -1, sizeof h); getchar(); // 过滤掉第一行最后的回程 int tot = 0; // 以下是最大闭合权子图的建图方式 for (int i = 1; i <= m; i ++ ) { int w, id; string line; getline(cin, line); stringstream ssin(line); ssin >> w; add(S, i, w); while (ssin >> id) add(i, m + id, INF); tot += w; } for (int i = 1; i <= n; i ++ ) { int p; cin >> p; add(m + i, T, p); } // 求最小割，找到最大权值 int res = dinic(); dfs(S); // dfs找到属于S集合的点 for (int i = 1; i <= m; i ++ ) // 如果当前的实验属于S集合 if (st[i]) printf("%d ", i); puts(""); for (int i = m + 1; i <= m + n; i ++ ) // 如果当前的仪器属于S集合 if (st[i]) printf("%d ", i - m); puts(""); printf("%d\n", tot - res); // 最大权闭合子图的权值 = 闭合子图内所有权值为正数的点权和-最小割 return 0; }

3.2.3 最大密度子图

acwing2324. 生活的艰辛 题意： 已知公司中一共有 n 名员工，员工之间共有 m 对两两矛盾关系。如果将一对有矛盾的员工安排在同一个团队，那么团队的管理难度就会增大。一个团队的管理难度系数等于团队中的矛盾关系对数除以团队总人数。团队的管理难度系数越大，团队就越难管理。约翰希望给儿子安排的团队的管理难度系数尽可能大。请帮帮他。1≤n≤100,0≤m≤1000,1≤k≤n 题解： 对于一张原图，新加S,T两点。给原图的每个点都add(S,i,U,0),add(i,T,2g-di+U,0) //g是二分的密度，di代表这个点的度数。U是为了防止负数出现,对于原图的边add(u,v,1,1)。 然后有：C[S,T]=Vn + 2g|V’|-2|E’| //这里V是上面的含义，V’是选中的点，E’是子图的边数，那么对于每一个二分的g,我们去check是否满足C[S,T]-Vn<0，若满足就说明g可行。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 110, M = (1000 + N * 2) * 2, INF = 1e8; int n, m, S, T; int h[N], e[M], ne[M], idx; double f[M]; int d[N], cur[N]; int dg[N]; struct Edge { int a, b; }edges[M]; int ans; bool st[N]; void add(int a, int b, double c1, double c2) { e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx ++ ; e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx ++ ; } void build(double g) { // 建图 memset(h, -1, sizeof h); idx = 0; for (int i = 0; i < m; i ++ ) add(edges[i].a, edges[i].b, 1, 1); // 原图的边就边权为1 for (int i = 1; i <= n; i ++ ) { add(S, i, m, 0); // 从S到i点，权值为U add(i, T, m + g * 2 - dg[i], 0); // 从i点到V，权值为2g-di+U } } int bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(S); cur[S] = h[S]; d[S] = 0; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return 1; q.push(j); } } return 0; } double find(int u, double limit) { if (u == T) 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 <= 0) d[ver] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } } return flow; } double dinic(double g) { build(g); double r = 0, flow; while (bfs()) while (flow = find(S, INF)) r += flow; return r; } void dfs(int u) { st[u] = true; if (u != S) ans ++ ; for (int i = h[u]; ~i; i = ne[i]) { int ver = e[i]; if (!st[ver] && f[i] > 0) dfs(ver); } } int main() { scanf("%d%d", &n, &m); S = 0, T = n + 1; for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); dg[a] ++, dg[b] ++ ; // 计算每个点的度 edges[i] = {a, b}; } double l = 0, r = m; while (r - l > 1e-8) { // 二分枚举密度g double mid = (l + r) / 2; double t = dinic(mid); // 得到当前g的割值t if (m * n - t > 0) l = mid; // U取m else r = mid; } dinic(l); // 找到合适的g，然后做dinic，使得流量符合条件，为dfs做准备 dfs(S); // 找到密度子图的点 if (!ans) puts("1\n1"); // 如果只有一个点的清空 else { printf("%d\n", ans); // 打印所有dfs可达的点 for (int i = 1; i <= n; i ++ ) if (st[i]) printf("%d\n", i); } return 0; }

3.2.4 最小点权覆盖集

acwing2325. 有向图破坏 题意： 爱丽丝和鲍勃正在玩以下游戏。首先，爱丽丝绘制一个 N 个点 M 条边的有向图。然后，鲍勃试图毁掉它。在每一步操作中，鲍勃都可以选取一个点，并将所有射入该点的边移除或者将所有从该点射出的边移除。已知，对于第 i 个点，将所有射入该点的边移除所需的花费为 $W^{+}i$，将所有从该点射出的边移除所需的花费为 $W^{-}i$。鲍勃需要将图中的所有边移除，并且还要使花费尽可能少。请帮助鲍勃计算最少花费。$1\le N\le 100,1\le M\le 5000,1\le W^{+}i,W^{-}i\le 10^6$ 题解： 可以把每个点拆分为两个点$i^{+}$和$i^{-}$,然后对于$a$->$b$的边，转换为$a^{-}$->$b^{+}$的边，建图如下： 求最小割即可得到最小点权和。 对于打印方案，只需要dfs一遍得到S和T。然后枚举正向边即可。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 210, M = 5200 * 2 + 10, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } void dfs(int u) { st[u] = true; for (int i = h[u]; ~i; i = ne[i]) if (f[i] && !st[e[i]]) dfs(e[i]); } int main() { scanf("%d%d", &n, &m); S = 0, T = n * 2 + 1; memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) { int w; scanf("%d", &w); add(S, i, w); // 拆分为两个点，S->i-，权值为点权 } for (int i = 1; i <= n; i ++ ) { int w; scanf("%d", &w); add(n + i, T, w); // 拆分为两个点，i+->T，权值为点权 } while (m -- ) { int a, b; scanf("%d%d", &a, &b); add(b, n + a, INF); // a->b转换为a-->b+,权值为正无穷 } printf("%d\n", dinic()); // 求最小割 dfs(S); // 找到S集合和T集合 int cnt = 0; // 计算左部点到右部点的边数目 for (int i = 0; i < idx; i += 2) { int a = e[i ^ 1], b = e[i]; if (st[a] && !st[b]) cnt ++ ; } printf("%d\n", cnt); for (int i = 0; i < idx; i += 2) { int a = e[i ^ 1], b = e[i]; if (st[a] && !st[b]) { if (a == S) printf("%d +\n", b); // 和S相连的为左部点的点 } } for (int i = 0; i < idx; i += 2) { int a = e[i ^ 1], b = e[i]; if (st[a] && !st[b]) { if (b == T) printf("%d -\n", a - n); // 和T相连的为右部点的点 } } return 0; }

3.2.5 最大点权独立集

acwing2326. 王者之剑 题意： 给出一个 n×m 网格，每个格子上有一个价值 vi,j 的宝石。Amber 可以自己决定起点，开始时刻为第 0 秒。以下操作，在每秒内按顺序执行。

若第 i 秒开始时，Amber 在 (x,y)，则 Amber 可以拿走 (x,y) 上的宝石。在偶数秒时（i 为偶数），则 Amber 周围 4 格的宝石将会消失。若第 i 秒开始时，Amber 在 (x,y)，则在第 (i+1) 秒开始前，Amber 可以马上移动到相邻的格子 (x+1,y),(x−1,y),(x,y+1),(x,y−1) 或原地不动 (x,y)。

求 Amber 最多能得到多大总价值的宝石。 $1\le n,m\le 100,1\le vi,j\le 1000$ 题解： 仔细分析可知，最优的方案是选择所有相邻的点中的一个，然后就是求最大权点独立集。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5WWooKkb-1601723735436)(https://i.loli.net/2020/09/28/P2qn7so81aATUtC.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; const int N = 10010, M = 60010, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; int get(int x, int y) { return (x - 1) * m + y; } 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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { scanf("%d%d", &n, &m); S = 0, T = n * m + 1; memset(h, -1, sizeof h); int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int tot = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) { int w; scanf("%d", &w); // 只需要奇数点建图，然后按照最大点权覆盖集定义建图 if (i + j & 1) { add(S, get(i, j), w); for (int k = 0; k < 4; k ++ ) { int x = i + dx[k], y = j + dy[k]; if (x >= 1 && x <= n && y >= 1 && y <= m) add(get(i, j), get(x, y), INF); } } else add(get(i, j), T, w); tot += w; } printf("%d\n", tot - dinic()); // 所有点权和-最大点权覆盖集 return 0; }

acwing2199. 骑士共存问题 题意： 在一个 n∗n 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。对于给定的 n∗n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。 题解： 每个点可以向对应日字形位置连一条边，然后对于每一条边只能有一个骑士被选择，因此转化为最大点独立集问题。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 40010, M = 400010, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], ne[M], idx; int d[N], cur[N]; bool g[210][210]; int get(int x, int y) { return (x - 1) * n + y; } 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++; } // bfs找是否存在增广路 int bfs() { queue<int> q; memset(d, -1, sizeof d); q.push(S); d[S] = 0; cur[S] = h[S]; while(q.size()) { auto t = q.front(); q.pop(); for (int i = cur[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] != -1 || !f[i]) continue; d[j] = d[t] + 1; // 更新分层图 cur[j] = h[j]; // 当前弧优化，cur[j]记录j点第一条可以访问的边 if (j == T) return 1; q.push(j); } } return 0; } // dfs把增广路更新 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 j = e[i]; if (d[j] != d[u] + 1 || !f[i]) continue; // 必须在分层图上，防止出现环；必须有流量 int t = find(j, min(f[i], limit - flow)); // 找到从j出去的流量 if (!t) d[j] = -1; // 流量为0，说明这条路不行 f[i] -= t, f[i ^ 1] += t, flow += t; // 更新流量 } return flow; } int dinic() { int res = 0, flow = 0; // 每次判断是否存在增广路(bfs)，如果存在，那么把所有的增广路更新(find) while (bfs()) while(flow = find(S, INF)) res += flow; return res; } int main() { scanf("%d%d", &n, &m); S = 0, T = n * n + 1; memset(h, -1, sizeof h); while (m -- ) { int x, y; scanf("%d%d", &x, &y); g[x][y] = true; } int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; // 每个点和允许的日字形位置建一条边，然后按照最大点独立集的方式处理即可 int tot = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) { if (g[i][j]) continue; if (i + j & 1) { add(S, get(i, j), 1); for (int k = 0; k < 8; k ++ ) { int x = i + dx[k], y = j + dy[k]; if (x >= 1 && x <= n && y >= 1 && y <= n && !g[x][y]) add(get(i, j), get(x, y), INF); } } else add(get(i, j), T, 1); tot ++ ; } printf("%d\n", tot - dinic()); return 0; }

3.3 费用流

3.3.1 费用流之匹配问题

acwing2192. 运输问题 题意： W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 ai 个单位的货物；第 j 个零售商店需要 bj 个单位的货物。从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 $c_{ij}$。试设计一个将仓库中所有货物运送到零售商店的运输方案。对于给定的 m 个仓库和 n 个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。 题解： 源点S向每个仓库i连一条边，容量为a，费用为0；每个商店i向汇点连一条边，容量为b，费用为0；每个仓库向对应的商店连一条边，容量为正无穷，费用为c。求最小费用直接跑模板；求最大费用流，先还原网络，然后将费用取负，再求最小费用流，费用取反就是答案 代码：

#include <bits/stdc++.h> using namespace std; const int N = 160, M = 5150 * 2 + 10, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int 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++; } int spfa() { memset(d, 0x3f, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] <= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int main() { scanf("%d%d", &m, &n); S = 0, T = m + n + 1; memset(h, -1, sizeof h); for (int i = 1; i <= m; i ++ ) { int a; scanf("%d", &a); add(S, i, a, 0); // 源点S向每个仓库i连一条边，容量为a，费用为0 } for (int i = 1; i <= n; i ++ ) { int b; scanf("%d", &b); add(m + i, T, b, 0); // 每个商店i向汇点连一条边，容量为b，费用为0 } for (int i = 1; i <= m; i ++ ) // 每个仓库向对应的商店连一条边，容量为正无穷，费用为c for (int j = 1; j <= n; j ++ ) { int c; scanf("%d", &c); add(i, m + j, INF, c); } printf("%d\n", EK()); // 求最小费用流 // 还原网络，然后将费用取负，再求最小费用流，费用取反就是答案 for (int i = 0; i < idx; i += 2) { f[i] += f[i ^ 1], f[i ^ 1] = 0; w[i] = -w[i], w[i ^ 1] = -w[i ^ 1]; } printf("%d\n", -EK()); return 0; }

acwing2194. 负载平衡问题 题意： G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。数据保证一定有解。1≤n≤100,每个仓库的库存量不超过 100。 题解： 把每个货仓内的货物加起来求均值，可以计算出来每个货仓最后的货物数目。这些货仓分为两批，一批左部点，货物数目小于均值；另一批右部点，货物数目大于均值。对于左部点，货物数目小于均值，汇点S向i点连边，容量为a[i]-tot,费用为0；对于右部点，货物数目大于均值，i点向汇点T连边，容量为tot-a[i],费用为0；同时每个货仓需要向相邻点连边，容量为正无穷，费用为1 代码：

#include <bits/stdc++.h> using namespace std; const int N = 110, M = 610, INF = 1e8; int e[M], h[M], w[M], idx, ne[M], d[N], incf[N], f[M], pre[N], st[N]; // d[i]到达i点的最小花费和，incf[i]到达i点的最大流 int n, m, S, T; int a[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++; } // spfa找到最小花费的增广路 int spfa() { memset(d, 0x3f, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] <= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } void EK(int& flow, int& cost) { flow = cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } } int main() { memset(h, -1, sizeof h); cin >> n; S = 0, T = n + 1; int tot = 0; for (int i = 1; i <= n; ++i) { scanf("%d", a + i); tot += a[i]; // 向相邻的点连边 add(i, i < n? i + 1: 1, INF, 1); add(i, i > 1? i - 1: n, INF, 1); } tot /= n; // 计算每个点的最后货物数目 for (int i = 1; i <= n; ++i) { if (tot < a[i]) add(S, i, a[i] - tot, 0); // 货物数目小于均值，汇点S向i点连边，容量为a[i]-tot,费用为0 else if (tot > a[i]) add(i, T, tot - a[i], 0); // 货物数目大于均值，i点向汇点T连边，容量为tot-a[i],费用为0 } int flow, cost; EK(flow, cost); // 类EK算法求最小费用最大流 printf("%d\n", cost); return 0; }

acwing2193. 分配问题 题意： 有 n 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 cij。试设计一个将 n 件工作分配给 n 个人做的分配方案。对于给定的 n 件工作和 n 个人，计算最优分配方案和最差分配方案。1≤n≤50,0≤cij≤100 题解： 源点S向每个人连一条边，容量为1，费用为0；每个任务向汇点连一条边，容量为1，费用为0； 每个人向其对应的任务连一条边，容量为1，费用为c 代码：

#include <bits/stdc++.h> using namespace std; const int N = 110, M = 5210, INF = 1e8; int n, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int 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++; } // spfa找到最小花费的增广路 int spfa() { memset(d, 0x3f, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] <= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int main() { scanf("%d", &n); S = 0, T = n * 2 + 1; memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) { add(S, i, 1, 0); // 源点S向每个人连一条边，容量为1，费用为0 add(n + i, T, 1, 0); // 每个任务向汇点连一条边，容量为1，费用为0 } for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) { int c; scanf("%d", &c); add(i, n + j, 1, c); // 每个人向其对应的任务连一条边，容量为1，费用为c } printf("%d\n", EK()); // 最大流最小费用流 for (int i = 0; i < idx; i += 2) {// 还原网络，边权取负，跑最大流最小费用 f[i] += f[i ^ 1], f[i ^ 1] = 0; w[i] = -w[i], w[i ^ 1] = -w[i ^ 1]; } printf("%d\n", -EK()); // 费用取负为最大费用 return 0; }

acwing2184. 餐巾计划问题 题意： 1个餐厅在相继的 N 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri 块餐巾 (i=1,2,…,N)。餐厅可以购买新的餐巾，每块餐巾的费用为 p 分；或者把旧餐巾送到快洗部，洗一块需 m 天，其费用为 f 分；或者送到慢洗部，洗一块需 n 天，其费用为 s 分。餐厅每天使用的餐巾必须是今天刚购买的，或者是今天刚洗好的，且必须恰好提供 ri 块毛巾，不能多也不能少。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划，使总的花费最小。 题解： 每天产生r条旧毛巾，源点S->i,容量为r，费用为0;每天产生r条旧毛巾，i+n->T，容量为r，费用为0;旧毛巾送到快洗部，i向i+n+x，容量为正无穷，费用为xp;旧毛巾送到慢洗部，i向i+n+y，容量为正无穷，费用为yp [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Wzp7yriN-1601723735437)(https://i.loli.net/2020/09/26/vCAo1r6Ywc9WZXg.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; const int N = 1610, M = 10000, INF = 1e8; int n, p, x, xp, y, yp, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int 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++; } // spfa找到最小花费的增广路 int spfa() { memset(d, 0x3f, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] <= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int main() { scanf("%d%d%d%d%d%d", &n, &p, &x, &xp, &y, &yp); S = 0, T = n * 2 + 1; memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) { int r; scanf("%d", &r); add(S, i, r, 0); // 每天产生r条旧毛巾，源点S->i,容量为r，费用为0 add(n + i, T, r, 0); // 每天产生r条旧毛巾，i+n->T，容量为r，费用为0 add(S, n + i, INF, p); // 可以购买无限条毛巾，S->n+1,容量正无穷，费用为p if (i < n) add(i, i + 1, INF, 0); if (i + x <= n) add(i, n + i + x, INF, xp); // 旧毛巾送到快洗部，i向i+n+x，容量为正无穷，费用为xp if (i + y <= n) add(i, n + i + y, INF, yp); // 旧毛巾送到慢洗部，i向i+n+y，容量为正无穷，费用为yp } printf("%d\n", EK()); return 0; }

3.3.2 费用流之最大权不相交问题

acwing2191. 数字梯形问题 题意： 给定一个由 n 行数字组成的数字梯形如下图所示。 梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。 规则 1：从梯形的顶至底的 m 条路径互不相交。 规则 2：从梯形的顶至底的 m 条路径仅在数字结点处相交。 规则 3：从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。 对于给定的数字梯形，分别按照规则 1，规则 2，和规则 3 计算出从梯形的顶至底的 m 条路径，使这 m 条路径经过的数字总和最大。1≤n,m≤20,梯形中的数字范围 [1,1000]。 题解： 针对问题一： 每一个点只能用一次,拆点,容量为一,费用为w[i].如果是第1行，那么源点S点向该点连边，容量为1，费用为0.如果是第n行，那么该点向汇点T连边，容量为1，费用为0 针对问题二： 把拆点内部的边权置为正无穷 针对问题三： 把拆点内部的边权置为正无穷，把向左下角和右下角的边边权为正无穷。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 1200, M = 4000, INF = 1e8; int m, n, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int d[N], pre[N], incf[N]; bool st[N]; int id[40][40], cost[40][40]; 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 ++ ; } // spfa找最长路 int spfa() { memset(d, 0xc0, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] >= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int main() { int cnt = 0; scanf("%d%d", &m, &n); S = ++ cnt; T = ++ cnt; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m + i - 1; j ++ ) { scanf("%d", &cost[i][j]); id[i][j] = ++ cnt; } // 规则1 memset(h, -1, sizeof h), idx = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m + i - 1; j ++ ) { add(id[i][j] * 2, id[i][j] * 2 + 1, 1, cost[i][j]); // 每个点拆分为两个点，入点向出点连一条容量为1，费用为数值的边 if (i == 1) add(S, id[i][j] * 2, 1, 0); // 如果是1，那么源点S点向该点连边，容量为1，费用为0 if (i == n) add(id[i][j] * 2 + 1, T, 1, 0); // 如果是n，那么该点向汇点T连边，容量为1，费用为0 if (i < n) {// 如果不是最后一行，那么向左下角和右下角分别连边，容量为1，费用为0 add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0); add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0); } } printf("%d\n", EK()); // 规则2 memset(h, -1, sizeof h), idx = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m + i - 1; j ++ ) { add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]); // 这里改成INF if (i == 1) add(S, id[i][j] * 2, 1, 0); if (i == n) add(id[i][j] * 2 + 1, T, INF, 0); // 这里改成INF if (i < n) { add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0); add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0); } } printf("%d\n", EK()); // 规则3 memset(h, -1, sizeof h), idx = 0; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m + i - 1; j ++ ) { add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);// 这里改成INF if (i == 1) add(S, id[i][j] * 2, 1, 0); if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);// 这里改成INF if (i < n) { add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0);// 这里改成INF add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0);// 这里改成INF } } printf("%d\n", EK()); return 0; }

3.3.3 费用流之网格图模型

acwing382. K取方格数 题意： 在一个N*N的矩形网格中，每个格子里都写着一个非负整数。可以从左上角到右下角安排K条路线，每一步只能往下或往右，沿途经过的格子中的整数会被取走。若多条路线重复经过一个格子，只取一次。求能取得的整数的和最大是多少。 题解： 方格内每个点拆分为两个点，第一个点向第二个点连边，连一条容量为1，费用为t的边；第一个点向第二个点连一条容量为正无穷，费用为0的边。每个点向它的下一个点连一条边，容量为正无穷，费用为0。每个点向它的右边一个点连一条边，容量为正无穷，费用为0。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3MQiuN5x-1601723735438)(https://i.loli.net/2020/09/26/LZeDgiWfp5wVPxE.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; const int N = 5010, M = 30010, INF = 1e8; int n, k, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int 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 ++ ; } // spfa找最长路 int spfa() { memset(d, 0xc0, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] >= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int get(int i, int j, int t ){ return (i * n + j) * 2 + t; } int main() { memset(h, -1, sizeof h); cin >> n >> k; S = 2 * n * n + 5, T = S + 1; add(S, get(0, 0, 0), k, 0); add(get(n - 1, n - 1, 1), T, k, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int t; scanf("%d", &t); add(get(i, j, 0), get(i, j, 1), 1, t); // 每个点拆分为两个点，连一条容量为1，费用为t的边 add(get(i, j, 0), get(i, j, 1), INF, 0); // 每个点拆分为两个点，连一条容量为正无穷，费用为0的边 if (i + 1 < n) add(get(i, j, 1), get(i + 1, j, 0), INF, 0); // 每个点向它的下一个点连一条边，容量为正无穷，费用为0 if (j + 1 < n) add(get(i, j, 1), get(i, j + 1, 0), INF, 0); // 每个点向它的右边一个点连一条边，容量为正无穷，费用为0 } } printf("%d\n", EK()); return 0; }

acwing2195. 深海机器人问题 题意： 深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间占据同一位置。用一个 P×Q 网格表示深海机器人的可移动位置。西南角的坐标为 (0,0)，东北角的坐标为 (P,Q)。 给定每个深海机器人的出发位置和目标位置，以及每条网格边上生物标本的价值。计算深海机器人的最优移动方案，使深海机器人到达目的地后，采集到的生物标本的总价值最高。1≤a≤4,1≤b≤6,1≤P,Q≤15,1≤k,r≤10,0≤x≤P,0≤y≤Q,各个生物标本价值不超过 200 题解： 源点向起始点S连边，容量为k，费用为0；终点向汇点T连边，容量为r，费用为0；每个点向相邻点连两条边，第一条容量为1，费用为c，第二条容量为正无穷，费用为0。 代码：

#include <bits/stdc++.h> using namespace std; const int N = 260, M = 2000, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int d[N], pre[N], incf[N]; bool st[N]; int get(int x, int y) { return x * (m + 1) + y; } 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 ++ ; } // spfa找最长路 int spfa() { memset(d, 0xc0, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] >= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int main() { int A, B; scanf("%d%d%d%d", &A, &B, &n, &m); S = (n + 1) * (m + 1), T = S + 1; memset(h, -1, sizeof h); for (int i = 0; i <= n; i ++ ) for (int j = 0; j < m; j ++ ) { int c; scanf("%d", &c); add(get(i, j), get(i, j + 1), 1, c); // 每个点向相邻点连两条边，第一条容量为1，费用为c add(get(i, j), get(i, j + 1), INF, 0); // 第二条容量为正无穷，费用为0 } for (int i = 0; i <= m; i ++ ) for (int j = 0; j < n; j ++ ) { int c; scanf("%d", &c); add(get(j, i), get(j + 1, i), 1, c); add(get(j, i), get(j + 1, i), INF, 0); } while (A -- ) { int k, x, y; scanf("%d%d%d", &k, &x, &y); add(S, get(x, y), k, 0); // 源点向起始点S连边，容量为k，费用为0 } while (B -- ) { int r, x, y; scanf("%d%d%d", &r, &x, &y); add(get(x, y), T, r, 0); // 终点向汇点T连边，容量为r，费用为0 } printf("%d\n", EK()); return 0; }

3.3.4 费用流之上下界可行流

acwing969. 志愿者招募 题意： 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要 N 天才能完成，其中第 i 天至少需要 Ai 个人。布布通过了解得知，一共有 M 类志愿者可以招募。其中第 i 类可以从第 Si 天工作到第 Ti 天，招募费用是每人 Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。数据保证一定有解。1≤N≤1000，1≤M≤10000 ，题目中其他所涉及的数据均不超过$2^{31}-1$。 题解： 把每天需要的人转化为边，那么每天都最少需要Ai人，意味这边的容量A[i] ~ INF, 费用为0；每个人可以从Ti ~ Si,意味着从Si+1->Ti有边，容量为0 ~ INF,费用为ci。然后再按照无源汇上下界可行流的方法建图即可： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B84Hp9u5-1601723735443)(https://i.loli.net/2020/09/26/vt1QUAiVq4xflum.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; const int N = 1010, M = 24010, INF = 1e8; int n, m, S, T; int h[N], e[M], f[M], w[M], ne[M], idx; int 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 ++ ; } int spfa() { memset(d, 0x3f, sizeof d); memset(incf, 0, sizeof incf); queue<int> q; q.push(S); st[S] = 1; d[S] = 0; incf[S] = INF; while(q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (!f[i] || d[j] <= d[t] + w[i]) continue; // 如果流为0或者花费变大，不走 d[j] = d[t] + w[i]; // 更新花费 pre[j] = i; // 记录当前点的前一条边 incf[j] = min(f[i], incf[t]); // 更新最大流 if (!st[j]) { q.push(j); st[j] = 1; } } } return incf[T] > 0; } int EK() { int flow = 0; int cost = 0; while(spfa()) { // 如果能够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; // 更新点 } } return cost; } int main() { scanf("%d%d", &n, &m); S = 0, T = n + 2; memset(h, -1, sizeof h); int last = 0; for (int i = 1; i <= n; i ++ ) { int cur; scanf("%d", &cur); // 无源汇上下界可行流模板建边方法 if (last > cur) add(S, i, last - cur, 0); else if (last < cur) add(i, T, cur - last, 0); //对于一天 i，让 i 点向 i+1 点连边。流量下界是 Ai、上界是正无穷，费用是 0，这条边的流量意味着第 i 天的工作人数 add(i, i + 1, INF - cur, 0); last = cur; } add(S, n + 1, last, 0); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); // 对于一类志愿者 j，让 Tj+1 向 Sj 连一条容量无界限，费用是 Ci 的边，这条边可以自由活动，意味着自由安排是志愿者。 add(b + 1, a, INF, c); } printf("%d\n", EK()); return 0; }