【转载】 网络流与线性规划 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. ，表示路径的终点，流量通常为 ，费用通常为 。

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

线性规划网络优化

涉案题目：

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

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

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

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