最大流，最小割和匹配（一）

[[ slider_text ]]

[[ item.c ]]

最大流，最小割和匹配（一）

发布时间 2025-04-18 作者：zhangminchen 来源：算法小站

流和匹配

## 最大流问题
### 二分图匹配问题
源点向每个点连$$1$$的流量，每个点向汇点连$$1$$的流量
二分图原来就有的边，连$$+\infty$$的流量
在图上跑一遍最大流，就得到了一个最大匹配

证明，因为每个点通往源，汇的流量上限都是$$1$$，所以每个点最多只会被用到一次

**[网络流 24 题 试题库](https://ac.nowcoder.com/acm/problem/213904)**
给定$$n$$道试题，每一道试题标明了所属的类别，同一道题可能属于多个类别属性
现在需要抽出$$m$$题组成试卷，并且要求试卷包含指定类型的试题，计算方案

**算法分析**
1）考虑到$$n$$道题，不一定每一题都要出，但是一道题有多个 tag，怎么来描述这件事情呢？
可以看作是**匹配**，比如一道题有 3 个知识点，可以看作`(tag1, tag2, tag3) <--> (item1)`相匹配

2）考虑限制，比如 tag1 要出 3 道题，怎么办呢？
不妨设包含 tag1 的题目有`(item1, item2, ....., itemk)`，要在`item[1...k]`中选 3 题
可以考虑对于每个$$(tag_1, item_i)$$连一条流量上限为$$1$$的边
同时$$s \to tag_1$$连一条流量上限为$$3$$的边

3）注意到一道题目出一次，你不能出重复的题目，所以对每个$$item_i \to t$$连流量上限为$$1$$的边

4）最后还有一个问题，怎么判断是否合法？只需要看`dinic() == (S 流出去的所有流量)`，即判断满流即可
`S 流出去的所有流量`，在输入的时候即可计算出来
那方案数呢？实际上，对于$$(u, v), u \in \text{tag}, v \in \text{item}$$，如果$$flow(u, v) = 1$$
它实际上真的流了$$1$$的流量，就可以认为是`u 这个知识点，选择出题目 v`

> 输出的时候，注意一下，右边那一排关于 item 的点，编号是`k + j`，对应到实际的题目，应该是`v - k`

### Dicing
**[POI 2005 Dicing](https://ac.nowcoder.com/acm/problem/211215)**
**问题描述**
很多局游戏，知道每一局游戏对弈的是哪两个选手。每局游戏有一个赢家，现在要你找到能够赢最多的那个人
并且决策那个人**最少**会赢多少场
就是让赢得多的人，赢得场次尽可能少

#### 算法分析
> 这又是一个最大值最小的问题，可以考虑二分答案，赢得最多的那个人赢了$$x$$场，最小化这个$$x$$

判断的时候，考虑是不是所有玩家赢的场数都$$\leqslant x$$

> 怎么来进一步分析呢？

这实际上也是一个分配问题，注意到一局游戏只有一个赢家，也就是说**要为每一个游戏分配一个玩家**
有什么限制呢？那就是一个游戏只能被选一次（分配完了之后，就不会再选这个游戏了）
可以考虑从`s -> 游戏`连一条流量上限是`1`的边

那么玩家呢？一个玩家可能会赢好几场，二分$$x$$之后，每个玩家赢的场数$$\leqslant x$$
也就是说，每个玩家可以被**经过**的次数，上限就是$$x$$
此时`玩家 -> t`连一条流量上限是`x`的边即可

一局游戏 2 个玩家，游戏`u->v1, u->v2`分别连流量上限是`1`的边

什么时候有解呢？
那就是为每一个游戏，都找到一个**匹配玩家**，假设有$$m$$局游戏，那么必须满流，`dinic() == m`有解

### 卡点的流量
**[网络流 24 题 最长递增子序列问题](https://ac.nowcoder.com/acm/problem/213820)**
给定一个序列`x[1...n]`
1）计算其不下降子序列（非严格 LIS）的长度`s`
2）计算从给定的序列中最多能取出多少个长度为`s`的不下降子序列，要求每个数只能被选一次
3）如果允许在序列中多次取$$x_1, x_n$$，问从给定的序列中最多取多少个长度为`s`的不下降子序列

#### 算法分析
这里题目中，第二问要求取 LIS，每个数只能被选一次

>  求 LIS 很容易，难点在于，怎么根据这个 LIS 信息来建模？难点是怎么处理**一个数只能被选一次**这个问题

流实际上是一条路径，从$$s \to t$$的最大流，好像也能被看作是一种方案？
比如上升子序列$$a_i \leqslant a_j$$，那么能不能$$(i, j)$$连流量上限是$$1$$的边呢？

这样好像是可以做的，第一问用 dp 求解，如果$$dp_v = dp_u + 1$$，并且$$a_u \leqslant a_v$$
那么我们考虑$$u \to v$$连流量是$$1$$的边
注意到对于$$u$$而言，满足$$dp_u + 1$$的`v`可能有很多个，比如`dp(v1), dp(v2), dp(v3), ...`
都依次连边，这样就满足了**最长上升**这一限制

> 那么多种方案，并且**每个数只能被选一次**，怎么满足呢？

如果按照上述方法去构造，从`dp = 1`的点跑到`dp = n`的点，只能得到一种方案
解决方法是，$$s$$向每一个`dp = 1`的点连$$+\infty$$的边，同时所有`dp = n`的点向$$t$$连$$+\infty$$的边
这样跑最大流可以跑出多种方案

那么这样做又有一个问题
比如`5`这个点，有**多条出边**，那么在`5`这个点多路增广的时候，`5`会被选多次，怎么保证**只被选一次呢**？

> 一个点只选一次，考虑拆点，卡点的流量

之前说的，满足$$a_i \leqslant a_j, dp_j = dp_i + 1$$的$$i \to j$$，考虑拆点
预处理拆点，对于每个点$$i$$，在$$i \to i'$$连一条流量为$$1$$的边

建图的时候，根据 dp 值的关系，对$$(i, j)$$连边，拆成$$(i' \to j)$$连一条流量上限为$$1$$的边
（拆点的实现很简单，比如$$i' = i+n$$，就用来对应拆出来的点）

这样跑一遍$$s \to t$$的最大流就是答案

> 那么第三个条件$$x_1, x_n$$可以被选多次怎么办呢？

拆点的时候，$$(1, 1'), (n, n')$$连流量上限为$$+\infty$$的边即可

> 注意点，`dp(j) = dp(i) + 1`和`a[i] <= a[j]`两个条件要同时限制住

否则，比如说
```bash
5 11 16
5 8 9
都构成长度为 3 的 LIS，注意到 9 这个点的长度 dp(9) = 3 = dp(11) + 1
实际上 11，9 并不构成 LIS
```

另外还需特判，如果 LIS 的长度本身就是`1`，那么$$1, n$$是不能拆成$$(1, 1', +\infty), (n, n', +\infty)$$的

上一篇：积性函数，莫比乌斯反演（三）下一篇：2025年一月算法比赛（一）

看完文章有啥想法