【转载】 网络流与线性规划 24 题刷题指南

前言

本篇博文转载自博客园 ticmis 的博文 网络流24题 ，转载时做了如下改动：

1. 排版整理，规范化。
2. 题单中添加了 洛谷题号 和 洛谷难度。
3. 错别字修改。
4. 内容描述稍作改动。

说实话，本人很讨厌 某SDN 上的各个博主间互相抄来抄去的行为，这一篇是我第一次转载别人的博文，原因是我认为原博文讲的非常好，想搬到过来推广给大家。

题单列表

本人按照如下顺序整理的洛谷题单：网络流与线性规划 24 题 。

题单基本按照知识点难度排序，推荐读者以这个顺序做题。有相关建议可以在评论区提出。

编号	洛谷题号	题目名称	题目模型	转化模型	洛谷难度
	P2756	飞行员配对方案问题	二分图最大匹配	二分图	提高+/省选−
	P4011	孤岛营救问题	分层图最短路	最短路径	提高+/省选−
	P4009	汽车加油行驶问题	分层图最短路	最短路径	省选/NOI−
	P2761	软件补丁问题	最小转移代价	最短路径	提高+/省选−
	P2754	星际转移问题	分层图转移	最大流	省选/NOI−
	P2762	太空飞行计划问题	最大权闭合图	最小割	省选/NOI−
	P2764	最小路径覆盖问题	有向无环图最小路径覆盖	最大流	省选/NOI−
	P2765	魔术球问题	有向无环图最小路径覆盖	最大流	省选/NOI−
	P3254	圆桌问题	二分图多重匹配	最大流	提高+/省选−
	P2763	试题库问题	二分图多重匹配	最大流	提高+/省选−
	P4014	分配问题	二分图最佳匹配	费用流	提高+/省选−
	P2774	方格取数问题	二分图点权最大独立集	最小割	省选/NOI−
	P3355	骑士共存问题	二分图点权最大独立集	最小割	省选/NOI−
	P4016	负载平衡问题	费用流水题模板题	费用流	省选/NOI-
	P4015	运输问题	费用流水题模板题	费用流	提高+/省选−
	P2766	最长不下降子序列问题	限制性带权路径	费用流	省选/NOI−
	P2770	航空路线问题	限制性带权路径	费用流	省选/NOI−
	P4013	数字梯形问题	限制性带权路径	费用流	省选/NOI−
	P3358	最长k可重区间集问题	限制性带权路径	费用流	省选/NOI−
	P3357	最长k可重线段集问题	限制性带权路径	费用流	省选/NOI−
	P4012	深海机器人问题	限制性带权路径	费用流	省选/NOI−
	P3356	火星探险问题	限制性带权路径	费用流	省选/NOI−
	P1251	餐巾计划问题	限制性带权路径	费用流	省选/NOI−
	P2775	机器人路径规划问题	题目有误	题目有误	暂无评定

题型归纳

网络流题中所有出现过的题型整理如下。

图上状态转移

涉案题目：

编号	题目名称	题目模型	转化模型
	孤岛营救问题	分层图最短路径	最短路径
	汽车加油行驶问题	分层图最短路径	最短路径
	软件补丁问题	最小转移代价	最短路径
	星际转移问题	分层图转移	最大流

这类题的特征就是，由一个确定的状态可以通过有限的方案，转化为另外一种确定的状态，思路有点类似转移。

、、这三道题就是状压（没错，网络流里混进来的间谍），见图，一发或即可

其中第 4 题还有一点比较特殊，这道题的转移方案特别多，对应过来就是，图上的边特别特别多，多到无法存下来。咋办呢？由于点是确定且数量可以接受的，就跑最短路径的同时，“建”边即可。

而这道题稍微有一点难度。这道题和前三道题有所区分。它并不是单纯的状压，而用到网络流。

它的一个思维难点就在于时间是无法事先确定的，只能模拟。模拟的过程中，不断为某一天增边建图，然后跑最大流

有向无环图最小路径覆盖

涉案题目：

编号	题目名字	题目模型	转化模型
	最小路径覆盖问题	有向无环图最小路径覆盖	最大流
	魔术球问题	有向无环图最小路径覆盖	最大流

详情请参考博客 “网络流 最小路径覆盖” 和 “题解 魔术球问题”

二分图相关算法

涉案题目：

编号	题目名字	题目模型	转化模型
	飞行员配对方案问题	二分图最大匹配	二分图
	圆桌问题	二分图多重匹配	最大流
	试题库问题	二分图多重匹配	最大流
	分配问题	二分图最佳匹配	费用流

这类题就是用网络流的算法去解决二分图的问题。学习了网络流之后，再看二分图，感觉就比较简单了。简单的建图，简单的网络流即可一发带走 (•̀ ω •́ )y

不相交路径

涉案题目：

编号	题目名字	题目模型	转化模型
	最长递增子序列问题	限制性带权路径	最大流
	航空路线问题	限制性带权路径	费用流
	数字梯形问题	限制性带权路径	费用流
	最长k可重区间集问题	限制性带权路径	费用流
	最长k可重线段集问题	限制性带权路径	费用流
	深海机器人问题	限制性带权路径	费用流
	火星探险问题	限制性带权路径	费用流

第一眼看限制性带权路径的题，很容易让人感觉是搜索题。因为假如数据范围足够小，简单的搜索是能够保证正确性的。

但是，学完了网络流，可解决的数据范围肯定就要比搜索肥了不少

这类题的总体思路是拆点：

1. 将拆为和两个点，为入点，为出点。
2. ，流量表示这个点可以经过的次数，费用表示经过这个点的收益。
3. ，流量和费用表示从一个点转移到点，或者转移过程中点收益。
4. ，表示路径的起始点，流量为路径条数，费用通常为。
5. ，表示路径的终点，流量通常为，费用通常为。

然后，建图，一发入魂╰(￣ω￣ｏ)

线性规划网络优化

涉案题目：

编号	题目名字	题目模型	转化模型
	餐巾计划问题	线性规划网络优化	费用流

这类题就是用网络流来优化线性规划，由于线性规划本身就具有很强的灵活性，所以这类题也相应的具有很强的灵活性

说是“类”，其实也只见过两道题而已啊~~（＞人＜；）

餐巾计划这道题我认为是网络题（除去那道错题）中最难的一道题。建图很有创造性，通过建图，完美的表达了题目的限制条件的同时，又用上了费用流这个强大利器。