网络流学习笔记——最小费用最大流

想象这样一个场面：从自来水厂到你家有若干根水管，每根水管都有一个流量上限，还有一个单位流量的费用。

你现在不仅想要让流到你家的水尽量多，还想尽可能节省费用。这就是最小费用最大流问题了。

继续阅读网络流学习笔记——最小费用最大流

一个动态更新的洛谷综合题单

本项目已经在Github上开源，欢迎各位dalao前来围观/贡献！（求Star）

试炼场的题目确实很具有代表性，但是近几年以来，又有许多经典题目出现在OI界中，这个大题单就是作为试炼场的扩展和补充。

Copyleft

本项目采用知识共享署名-相同方式共享 4.0 国际许可协议以及附加的The Star And Thank Author License进行许可。

换言之，您可以自由的共享并演绎该项目，但是必须给出必要的署名，并以相同方式共享本项目，并为本项目的Github仓库点赞（Star）。

更新日志

1.1.1 2019/3/14：

  1. 问题修复：将后缀数组专题移动至省选字符串算法。

1.1 2019/3/13：

  1. 添加了新专题：非传统题，并在其中添加了提交答案题。
  2. 添加了新专题：省选字符串算法，并添加了KMP，Manacher算法的题目，将原来位于省选数据结构的Trie树和AC自动机两个小类移动到了该专题。
  3. 部分题目分类进行了调整。

1.0 2019/1/24：

  1. 再一次校对了题单，并修正了部分内容。
  2. 将题单发布至Github。

更早版本的更新日志请点击这里查看

Part 0 试机题

三道试机题目。

Part 1 入门阶段

本部分内容主要针对入门OIer。算法的成分不算太多，主要是语言方面的知识。

Part 1.1 程序三大结构——顺序，分支与选择结构

这些内容是程序设计的基础。

Part 1.2 数组基础

数组可以用于存储大量的信息。

Part 1.3 字符串基础

字符串是特殊的数组，但它也有很多自身的特点。

Part 1.4 函数，递归及递推

这是初学者最难理解的部分，建议画出递归图来理解递归的过程。

Part 2 普及组算法

这一部分的内容包含了OI中绝大多数的基本算法，供各位巩固基础。

Part 2.1 模拟

模拟，顾名思义就是题目要求你做什么你就做什么，这样的题目很考验选手的代码组织能力。

Part 2.2 排序算法

通过排序，我们可以将数据有序化，这让我们对数据的处理方便了很多。

Part 2.3 基础搜索

搜索可以穷举各种情况。很多题目都可以用搜索完成。就算不能，搜索也是骗分神器。

Part 2.3.1 深度优先搜索

深度优先搜索（DFS），即按照深度优先的顺序搜索的算法。

深度优先搜索一般使用栈来实现。

Part 2.3.2 广度优先搜索

广度优先搜索（BFS），即优先扩展浅层节点，逐渐深入的搜索算法。

广度优先搜索一般使用队列来实现。

Part 2.4 二分答案

对一个满足单调性质的问题，我们可以采用二分答案的方法来解决。

Part 2.5 分治

分治，即分而治之，将大问题分解为小问题，分别求解，最后合并结果。

Part 2.6 基础数据结构

普及组阶段可能考到的数据结构有：链表、栈、队列、二叉树。

这几种数据结构都比较基础，实现难度较低。

Part 2.6.1 链表

在一个数列中高效插入一个元素，链表毫无疑问是最好的选择。

Part 2.6.2 栈

栈，是一种后进先出（FILO）的数据结构。

Part 2.6.3 队列

队列，是一种先进先出（FIFO）的数据结构。

Part 2.6.4 二叉树

二叉树是一种特殊的树，它有很多特殊的性质。

Part 2.7 贪心

贪心，指的是决策时都采取当前最优解的算法。有的时候，这样做确实可以获得最优解。

Part 2.8 动态规划基础

普及组考察的动态规划都比较基础，难度一般也不会太高。

Part 2.8.1 线性动态规划

线性动态规划，即具有线性阶段划分的动态规划。

Part 2.8.2 背包动态规划

背包动态规划是线性动态规划中特殊的一类，NOIP中考到的次数也不少。

Part 2.9 高精度

在C++中，long long都无法表示我们需要的整数时怎么办？那就用高精度吧！

Part 3 提高组算法

算法的难度在这里又上了一个台阶，很多题目都需要多种算法间的结合。

Part 3.1 高级动态规划

提高组的动态规划要比普及组复杂的多，状态的设计和转移都是值得讨论的话题。

Part 3.1.1 区间动态规划

区间动态规划一般以区间作为动态规划的阶段。

Part 3.1.2 树形动态规划

树形动态规划，即在树上进行的动态规划。

因为树的递归性质，树形动态规划一般都是递归求解的。

Part 3.2 高级搜索

如何优化搜索的效率，让搜索算法拿到更多的分数？

我们在这里主要讨论记忆化搜索和剪枝这两种NOIP常用的搜索优化方法。

Part 3.2.1 记忆化搜索

通过将已经遍历的状态记录下来，从而减少重复的搜索量，这就是记忆化搜索。

动态规划的时候，记忆化搜索也是一种高效简洁的实现方式。

Part 3.2.2 搜索的剪枝

对于一些不必要搜索的部分，我们可以避免访问这些状态，从而提高搜索效率。

Part 3.3 数学

OI中的数学知识很多，也有些杂乱。当然，NOIP考到的数学知识范围并不算太大。

这里给出的是NOIP中较常考的数学内容，更多的数学知识可以在省选部分找到。

Part 3.3.1 整除相关

与整除相关的概念有很多，比较常用的有素数，最大公约数和欧拉函数。

Part 3.3.1.1 素数

素数，指的是除1和它本身之外没有其他约数的数。

Part 3.3.1.2 最大公约数

如果两个数有一个共同的约数，那么这个约数就被称为公约数。最大公约数就是指这两个数的所有公约数中，最大的一个。

求解两个数的最大公约数，可以采用欧几里得算法解决。

Part 3.3.1.3 欧拉函数

欧拉函数 $ \varphi (x) $ 表示了小于 $ x $ 的数字中，与 $ x $ 互质的数字个数。

Part 3.3.2 不定方程相关

求解不定方程 $ ax+by=c $ 往往可以引出不少话题。

特别地，满足 $ ax \equiv 1 ( \mod b ) $的 $ x $ 被称为 $ a $ 在 $ \mod b $ 意义下的乘法逆元，记作 $ a^{-1} $ 。

Part 3.3.3 博弈论

博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

Part 3.4 高级数据结构

虽然这些数据结构NOIP中并不一定会考察到，但这些数据结构都非常有用，并且也是学习更高级数据结构的基础。

Part 3.4.1 树状数组

树状数组是一种简洁高效的树形数据结构。

Part 3.4.2 线段树

线段树的通用性比树状数组更强，可以处理更多涉及区间操作的题目。

Part 3.4.3 并查集

并查集常用于处理一些不相交集合的合并和查询问题。

Part 3.4.4 堆

堆总是一棵完全树，堆中某个节点的值总是不大于或不小于其父节点的值。

Part 3.5 图论

图论是数学的一个分支，它以图为研究的对象。

Part 3.5.1 图的存储与遍历

这里的图论内容都比较简单，涉及图的存储以及遍历图的方式。

Part 3.5.2 最短路问题

很多题目都可以转化为最短路的模型。因此，掌握最短路算法非常重要。

Part 3.5.3 树上问题

作为一种特殊的图，树上的问题具有很多鲜明的特点。

Part 3.5.3.1 树的直径

树的直径被定义为树上最远的两点间的距离。

计算树的直径，可以通过两遍DFS解决。

Part 3.5.3.2 最近公共祖先

两个点的最近公共祖先，即两个点的所有公共祖先中，离根节点最远的一个节点。

求解最近公共祖先，常用的方法是树上倍增或者树链剖分。

Part 3.5.4 最小生成树

用 $ n-1 $ 条边将图上的 $ n $ 个点连接起来，就是最小生成树问题。

Part 3.5.5 拓扑排序

将一个有向无环图排序，使得所有排在前面的节点不能依赖于排在后面的节点，这就是拓扑排序。

Part 3.5.6 差分约束

差分约束要解决的问题是：求出一组 $ n $ 元不等式的一组解，使得所有约束关系都能得到满足。

Part 3.5.7 图的连通性相关

利用Tarjan算法，我们可以解决很多与图的连通性相关的问题。

Part 4 省选/NOI算法

省选考到的东西很多，这里列出代表性的题目，供大家参考。

Part 4.1 省选数据结构

数据结构的题目，只有尽可能多练，才能熟能生巧。

Part 4.1.1 分块

分块是一种非常通用的暴力方法，虽然效率不如线段树和树状数组，但可以解决很多线段树和树状数组处理不了的问题。

Part 4.1.2 点分治

Part 4.1.3 主席树

Part 4.1.4 平衡树

Part 4.1.5 树链剖分

Part 4.1.6 树套树

Part 4.1.7 动态树

Part 4.1.8 可持久化数据结构

可持久化数据结构实现了在更新信息的时候保留历史版本。

Part 4.2 省选动态规划

省选的动态规划往往要与其他算法结合，对选手思维的要求也很高。

Part 4.2.1 状态压缩动态规划

将一个状态压缩为一个整数（通常为二进制数），就可以在更为方便地进行状态转移的同时，达到节约空间的目的。

Part 4.2.2 倍增优化动态规划

利用倍增的方式，我们可以将状态转移的效率大大提高。

Part 4.2.3 数据结构优化动态规划

利用数据结构来维护已有信息，也可以达到优化状态转移的目的。

Part 4.2.4 单调队列优化动态规划

如果决策具有单调性，就可以考虑运用单调队列来优化动态规划的效率。

Part 4.2.5 斜率优化动态规划

通过用单调队列维护一个凸壳，来达到优化转移的目的。

Part 4.2.6 四边形不等式优化动态规划

利用四边形不等式，我们就可以提高一些区间动态规划的效率。

Part 4.2.7 数位统计类动态规划

统计一个区间中满足条件的数有多少，就是数位统计类动态规划。

Part 4.2.8 轮廓线动态规划

轮廓线动态规划（即常说的插头DP）是一种特殊的状压动态规划，通过以轮廓线为状态来实现状态转移。

Part 4.3 省选数学

真正进入了数学的海洋，这里的数学题类型繁多，思维难度也不小。

Part 4.3.1 概率与期望

概率和期望是紧密相连的，OI中往往会出现和概率期望相关的动态规划问题。

Part 4.3.2 线性代数

Part 4.3.2.1 矩阵

利用矩阵优化数列递推，可以实现复杂度从线性到对数级的转变。

Part 4.3.2.2 高斯消元

高斯消元可以用来求解方程组。

Part 4.3.2.3 线性基

线性基可以求解最大异或和的一类问题。

Part 4.3.3 组合数学

Part 4.3.4 多项式

对多项式的运算进行优化，从而能够解决规模更大的问题。

Part 4.3.5 莫比乌斯反演

Part 4.4 省选字符串算法

Part 4.4.1 KMP

KMP算法可以用来解决模式串匹配问题。

Part 4.4.2 Manacher

Manacher算法可以在线性时间内求出一个字符串的最长回文子串。

Part 4.4.3 Trie树

Part 4.4.4 AC自动机

Part 4.4.5 后缀数组

Part 4.5 省选搜索

省选的搜索要注意的细节很多，对代码效率的要求也比较高。

Part 4.5.1 双向搜索

在搜索时，如果能从初态和终态出发，同时进行搜索，就可以减小搜索树的规模，提高时间效率。

Part 4.5.2 A*

在BFS中，如果能设计一个合理的估价函数，就可以更快扩展到最优解。这就是A*算法。

Part 4.5.3 IDA*

像BFS那样，每次只扩展一层节点，却采用DFS方式来遍历搜索树，这就是迭代加深搜索。

再加上一个估价函数来减小搜索量，就是IDA*了。

Part 4.6 省选图论

更复杂的图论问题，有些问题还要借助数据结构才能得到解决。

Part 4.6.1 二分图

二分图上的不少问题都可以转化成网络流解决，当然也有独特的其他方法。

Part 4.6.2 网络流

网络流是图论中一个重要的分支，很多题目都可以通过建立网络流的模型来解决。

Part 4.6.2.1 最大流/最小割

最大流，即求网络中最大的流量。

最小割，即求一个边权最小的边集，使得源点和汇点不再连通。

可以证明，最大流=最小割，因此我们将最大流和最小割专题放在一起。

Part 4.6.2.2 费用流

在网络流中给边加上一个参数——费用，就出现了费用流。

Part 4.7 非传统题

在NOI等比赛中，非传统题正越来越频繁出现。

非传统题主要包括以下几类：提交答案题，交互题，通信题。

因为洛谷目前只支持提交答案题，因此这里暂时只列出提交答案题。

Part 4.7.1 提交答案题

给你一些输入，你只需要提交这些输入对应的答案，即为提交答案题。