网络流与线性规划 24 题
题单介绍
# 【转载】网络流与线性规划 24 题刷题指南
## 前言
本篇博文转载自博客园 ticmis 的博文 [网络流24题](https://www.cnblogs.com/ticmis/p/13211073.html)，转载时做了如下改动：
1. 排版整理，规范化 $\LaTeX$。
2. 题单中添加了 洛谷题号 和 洛谷难度。
3. 错别字修改。
4. 内容描述稍作改动。
是我认为原博文讲的非常好，想搬过来推广给大家。
## 题单列表
题单基本按照知识点难度排序，推荐读者以这个顺序做题。有相关建议可以在评论区提出。
| 编号 | 洛谷题号 | 题目名称 | 题目模型 | 转化模型 | 洛谷难度 |
| ---- | -------- | ------------------------------------------------------------ | ---------------------- | -------- | -------------------------------- |
| $1$ | P2756 | [飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756) | 二分图最大匹配 | 二分图 | [提高+/省选−](javascript:void 0) |
| $2$ | P4011 | [孤岛营救问题](https://www.luogu.com.cn/problem/P4011) | 分层图最短路 | 最短路径 | [提高+/省选−](javascript:void 0) |
| $3$ | P4009 | [汽车加油行驶问题](https://www.luogu.com.cn/problem/P4009) | 分层图最短路 | 最短路径 | [省选/NOI−](javascript:void 0) |
| $4$ | P2761 | [软件补丁问题](https://www.luogu.com.cn/problem/P2761) | 最小转移代价 | 最短路径 | [提高+/省选−](javascript:void 0) |
| $5$ | P2754 | [星际转移问题](https://www.luogu.com.cn/problem/P2754) | 分层图转移 | 最大流 | [省选/NOI−](javascript:void 0) |
| $6$ | P2762 | [太空飞行计划问题](https://www.luogu.com.cn/problem/P2762) | 最大权闭合图 | 最小割 | [省选/NOI−](javascript:void 0) |
| $7$ | P2764 | [最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764) | 有向无环图最小路径覆盖 | 最大流 | [省选/NOI−](javascript:void 0) |
| $8$ | P2765 | [魔术球问题](https://www.luogu.com.cn/problem/P2765) | 有向无环图最小路径覆盖 | 最大流 | [省选/NOI−](javascript:void 0) |
| $9$ | P3254 | [圆桌问题](https://www.luogu.com.cn/problem/P3254) | 二分图多重匹配 | 最大流 | [提高+/省选−](javascript:void 0) |
| $10$ | P2763 | [试题库问题](https://www.luogu.com.cn/problem/P2763) | 二分图多重匹配 | 最大流 | [提高+/省选−](javascript:void 0) |
| $11$ | P4014 | [分配问题](https://www.luogu.com.cn/problem/P4014) | 二分图最佳匹配 | 费用流 | [提高+/省选−](javascript:void 0) |
| $12$ | P2774 | [方格取数问题](https://www.luogu.com.cn/problem/P2774) | 二分图点权最大独立集 | 最小割 | [省选/NOI−](javascript:void 0) |
| $13$ | P3355 | [骑士共存问题](https://www.luogu.com.cn/problem/P3355) | 二分图点权最大独立集 | 最小割 | [省选/NOI−](javascript:void 0) |
| $14$ | P4016 | [负载平衡问题](https://www.luogu.com.cn/problem/P4016) | 费用流~~水题~~模板题 | 费用流 | [省选/NOI−](javascript:void 0) |
| $15$ | P4015 | [运输问题](https://www.luogu.com.cn/problem/P4015) | 费用流~~水题~~模板题 | 费用流 | [提高+/省选−](javascript:void 0) |
| $16$ | P2766 | [最长不下降子序列问题](https://www.luogu.com.cn/problem/P2766) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $17$ | P2770 | [航空路线问题](https://www.luogu.com.cn/problem/P2770) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $18$ | P4013 | [数字梯形问题](https://www.luogu.com.cn/problem/P4013) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $19$ | P3358 | [最长k可重区间集问题](https://www.luogu.com.cn/problem/P3358) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $20$ | P3357 | [最长k可重线段集问题](https://www.luogu.com.cn/problem/P3357) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $21$ | P4012 | [深海机器人问题](https://www.luogu.com.cn/problem/P4012) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $22$ | P3356 | [火星探险问题](https://www.luogu.com.cn/problem/P3356) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $23$ | P1251 | [餐巾计划问题](https://www.luogu.com.cn/problem/P1251) | 限制性带权路径 | 费用流 | [省选/NOI−](javascript:void 0) |
| $24$ | P2775 | [机器人路径规划问题](https://www.luogu.com.cn/problem/P2775) | 题目有误 | 题目有误 | [暂无评定](javascript:void 0) |
## 题型归纳
网络流 $24$ 题中所有出现过的题型整理如下。
### $\large\mathfrak{1st.}$ 图上状态转移
涉案题目：
| 编号 | 题目名称 | 题目模型 | 转化模型 |
| :--: | :----------------------------------------------------------: | :------------: | :------: |
| 2 | [孤岛营救问题](https://www.luogu.org/problemnew/show/P4011) | 分层图最短路径 | 最短路径 |
| 3 | [汽车加油行驶问题](https://www.luogu.org/problemnew/show/P4009) | 分层图最短路径 | 最短路径 |
| 4 | [软件补丁问题](https://www.luogu.org/problemnew/show/P2761) | 最小转移代价 | 最短路径 |
| 5 | [星际转移问题](https://www.luogu.org/problemnew/show/P2761) | 分层图转移 | 最大流 |
这类题的特征就是，由一个确定的状态可以通过有限的方案，转化为另外一种确定的状态，思路有点类似 $\text{dp}$ 转移。
$2$、$3$、$4$ 这三道题就是状压 $\text{dp}$（没错，网络流里混进来的间谍），见图，一发 $\text{SPFA}$ 或 $\text{Dijkstra}$ 即可
其中第 4 题还有一点比较特殊，这道题的转移方案特别多，对应过来就是，图上的边特别特别多，多到无法存下来。咋办呢？由于点是确定且数量可以接受的，就跑最短路径的同时，“建”边即可。
而 $5$ 这道题稍微有一点难度。这道题和前三道题有所区分。它并不是单纯的状压，而用到网络流。
它的一个思维难点就在于时间是无法事先确定的，只能模拟。模拟的过程中，不断为某一天增边建图，然后跑最大流
### $\large\mathfrak{2nd.}$ 有向无环图最小路径覆盖
涉案题目：
| 编号 | 题目名字 | 题目模型 | 转化模型 |
| :--: | :----------------------------------------------------------: | :--------------------: | :------: |
| $7$ | [最小路径覆盖问题](https://www.luogu.org/problemnew/show/P2764) | 有向无环图最小路径覆盖 | 最大流 |
| $8$ | [魔术球问题](https://www.luogu.org/problemnew/show/P2765) | 有向无环图最小路径覆盖 | 最大流 |
详情请参考博客 “网络流 最小路径覆盖” 和 “题解 魔术球问题”
### $\large\mathfrak{3rd.}$ 二分图相关算法
涉案题目：
| 编号 | 题目名字 | 题目模型 | 转化模型 |
| :--: | :----------------------------------------------------------: | :------------: | :------: |
| $1$ | [飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756) | 二分图最大匹配 | 二分图 |
| $9$ | [圆桌问题](https://www.luogu.org/problemnew/show/P3254) | 二分图多重匹配 | 最大流 |
| $10$ | [试题库问题](https://www.luogu.org/problemnew/show/P2763) | 二分图多重匹配 | 最大流 |
| $11$ | [分配问题](https://www.luogu.org/problemnew/show/P4014) | 二分图最佳匹配 | 费用流 |
这类题就是用网络流的算法去解决二分图的问题。学习了网络流之后，再看二分图，感觉就比较简单了。简单的建图，简单的网络流即可一发带走 (•̀ ω •́ )y
### $\large\mathfrak{4th.}$ 不相交路径
涉案题目：
| 编号 | 题目名字 | 题目模型 | 转化模型 |
| :--: | :----------------------------------------------------------: | :------------: | :------: |
| $16$ | [最长递增子序列问题](https://www.luogu.org/problemnew/show/P2766) | 限制性带权路径 | 最大流 |
| $17$ | [航空路线问题](https://www.luogu.org/problemnew/show/P2770) | 限制性带权路径 | 费用流 |
| $18$ | [数字梯形问题](https://www.luogu.org/problemnew/show/P4013) | 限制性带权路径 | 费用流 |
| $19$ | [最长k可重区间集问题](https://www.luogu.org/problemnew/show/P3358) | 限制性带权路径 | 费用流 |
| $20$ | [最长k可重线段集问题](https://www.luogu.org/problemnew/show/P3357) | 限制性带权路径 | 费用流 |
| $21$ | [深海机器人问题](https://www.luogu.org/problemnew/show/P4012) | 限制性带权路径 | 费用流 |
| $22$ | [火星探险问题](https://www.luogu.org/problemnew/show/P3356) | 限制性带权路径 | 费用流 |
第一眼看限制性带权路径的题，很容易让人感觉是搜索题。因为假如数据范围足够小，简单的搜索是能够保证正确性的。
但是，学完了网络流，可解决的数据范围肯定就要比搜索肥了不少
这类题的总体思路是拆点：
1. 将 $x$ 拆为 $x_1$ 和 $x_2$ 两个点，$x_1$ 为入点，$x_2$ 为出点。
2. $x_1 \rightarrow x_2$，流量表示这个点可以经过的次数，费用表示经过这个点的收益。
3. $x_2 \rightarrow y_1$，流量和费用表示从一个 $x$ 点转移到 $y$ 点，或者转移过程中点收益。
4. $s \rightarrow x_1$，表示路径的起始点，流量为路径条数，费用通常为 $0$。
5. $x_2 \rightarrow t$，表示路径的终点，流量通常为 $\inf$，费用通常为 $0$。
然后，建图，一发入魂╰(￣ω￣ｏ)
### $\large\mathfrak{5th.}$ 线性规划网络优化
涉案题目：
| 编号 | 题目名字 | 题目模型 | 转化模型 |
| :--: | :---------------------------------------------------------: | :--------------: | :------: |
| $23$ | [餐巾计划问题](https://www.luogu.org/problemnew/show/P1251) | 线性规划网络优化 | 费用流 |
这类题就是用网络流来优化线性规划，由于线性规划本身就具有很强的灵活性，所以这类题也相应的具有很强的灵活性
说是“类”，其实也只见过两道题而已啊~~（＞人＜；）
餐巾计划这道题我认为是网络 $24$ 题（除去那道错题）中最难的一道题。建图很有创造性，通过建图，完美的表达了题目的限制条件的同时，又用上了费用流这个强大利器。