前言

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

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

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

题单列表

本人整理的洛谷题单：网络流与线性规划 24 题。

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

题型归纳

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

\(\large\mathfrak{1st.}\) 图上状态转移

涉案题目：

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

\(2\)、\(3\)、\(4\) 这三道题就是状压 \(\text{dp}\)（没错，网络流里混进来的间谍），见图，一发 \(\text{SPFA}\) 或 \(\text{Dijkstra}\) 即可

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

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

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

\(\large\mathfrak{2nd.}\) 有向无环图最小路径覆盖

涉案题目：

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

\(\large\mathfrak{3rd.}\) 二分图相关算法

涉案题目：

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

\(\large\mathfrak{4th.}\) 不相交路径

涉案题目：

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

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

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

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.}\) 线性规划网络优化

涉案题目：

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

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

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