前言
开坑了，开坑了
所谓网络流 24 题就是指 24 种经典的网络流建图模型。
本文内容顺序按照本人 A 题顺序排列。
试题库问题
题意
有 $n$ 道题和 $k$ 种类型，对于每道题，它匹配 $p_i$ 种类型，对于每种类型需要 $q_i$ 道题，现给出数据，求是否存在可行的情况满足每种类型的需求。
做法
很明显了，对于每道题，将他和它所对应的每个类型建边，边权为 $1$，在与源点建边，边权为 INF ，在对于每个种类，将其与汇点建边，边权为 $q_i$。
Code
方格取数问题
题意
有一个 $n$ 行，$m$ 列的矩阵，每个位置有一个权值 $a_{i,j}$，现在从这些数中挑选出一些，且不能同时挑选与自己有边相邻的权值，问怎样挑选结果最大。
做法
首先需要知道 $\text{最大和} = \text{总和} - \text{最小舍弃}$，而 $\text{最小舍弃} = \text{最小割} = \text{最大流}$。
然后是建图问题，对于第 $i$ 行，第 $j$ 列的点，如果 $i+j \equiv 1 \pmod 2$ 就连到源点，反之连到汇点，边权为 $a_{i,j}$，再将其与四周的点相连，边权为 INF，然后跑网络流就行了。
Code
飞行员配对方案问题
题意
有 $m$ 个外籍飞行员，$n-m$ 个英籍飞行员，有多组 $u$ 和 $v$，表示第 $u$ 位外籍飞行员能和第 $v$ 位英籍飞行员相互配合，询问最大匹配（同籍飞行员之间不可相互配合）。
做法
就是二分图最大匹配，没什么好说的，输出的时候判断一下，该边编号异或 $1$ 的边的边权是否大于零即可。
Code
圆桌问题
题意
有 $m$ 组个人，$n$ 张桌子，第 $i$ 组人有 $r_i$ 个人，第 $i$ 张桌子能坐 $c_i$ 个人，且同一组人不能坐一张桌子，询问这些桌子能不能坐的开，若可以，则输出一种方案。
做法
经典二分图求最大匹配。
首先，将每一组人和每一张桌子建点，再将源点与每一组人建边，边权为 $r_i$，将每一张桌子与汇点建边，边权为 $c_i$，再将每一组人与每一张桌子建边，边权为 $1$，再跑最大匹配即可。
Code
最小路径覆盖问题
题意
给你一张有向图 $G(V,E)$，求最小路径覆盖
做法
最小路径覆盖就是求最少的几条路径使得经过所有的点。
考虑合并，最大路路径覆盖是 $n$ 肯定没错，那最小呢，我们考虑合并一些点，是不是很熟悉了，二分图最大匹配，求出来即可。
Code
运输问题
题意
有 $n$ 个仓库和 $m$ 个商店，每个仓库里有 $a_i$ 件货物，每个商店需要 $b_i$ 件货物，从第 $i$ 个仓库往第 $j$ 个商店运每单位货物需要花费 $c_{i,j}$，问最小花费。
保证 $\sum\limits_{i=1}^n a_i=\sum\limits_{j=1}^m b_j$。
做法
一眼费用流，考虑建二分图。
首先对于每个商店，将其连到汇点，流量设为 $b_i$，费用为 $0$，对于每个仓库，将源点连向它，流量设为 $a_i$，费用为 $0$，然后对于每对 $i,j(1 \leq i \leq n,1 \leq j \leq m)$ 连一条边，流量 $INF$，费用 $c_{i,j}$。
然后跑费用流。
Code
负载平衡问题
题意
有 $m$ 个仓库，每个仓库有库存不等，求让每个仓库库存相等所需搬运的值（每个仓库只能往相邻的仓库搬东西）。
做法
很明显对于每个仓库我们将其与相邻两个仓库建边，流量为 $INF$，费用为 $1$（记得特判 $1$ 和 $n$）。
现在的主要问题是哪些点连远点，哪些点连汇点。
我们可以这么想，对于一个点，如果它的库存大于平均库存，就把他连到原点，流量为 $\text{库存}-\text{平均库存}$，如果它的库存小于平均库存，就连到汇点，流量为 $\text{平均库存}-\text{库存}$。
跑费用流即可。
Code
分配问题
题意
有 $n$ 个人和 $n$ 件工作，第 $i$ 个人做第 $j$ 件工作的效益为 $c_{i,j}$，问你最大效益和最小效益。
做法
明显二分图最大匹配，对于第 $i$ 个人将其与每件工作建边，边权为 $c_{i,j}$，然后，再对于每个人将其与源点建边，边权为 $INF$，对于每件工作，将其与汇点建边，边权为 $INF$，跑最大流即可。
Code
骑士共存问题
题意
有 $n^2$ 匹马（每匹马的走法参照象棋）和 $m$ 个障碍，问如何摆放使得场上的马最多且不能相互攻击。
做法
可以参照方格取数问题，不再过多说明。
Code
最长不下降子序列问题
题意
给你一个数组 $a$，求数组中的最长不下降子序列，有多少个不重复的最长不下降子序列和 $a_1$ 和 $a_n$ 可以多次取时，有多少个除 $a_1,a_n$ 外的最长不下降子序列。
做法
好题。
第一问可以直接大暴力 DP，不用多说。
对于第二问我们考虑拆点。对于每个 $a_i$ 我们拆成两个点，建边，如果 $f_i=\max\limits^n_{j=1} f_j$ 就，将其的第二个点连到汇点，如果 $f_i=1$ 就将其的第一个点连到原点，边权分别为 $1$，然后跑最大流。
对于第三问，我们就对于第一个点和最后一个点连向自己，源点和汇点的边的边权改为 $INF$ 即可。如果你不想再重新建边，就另外加一条边，然后再跑最大流即可。
Code
最长k可重区间集问题
题意
对于一个开区间集合 $I$，从中选取一个开区间集合 $S \subseteq I$，再从数轴上取一个数 $x$，如果在开区间集合 $S$，中包含 $x$ 的开区间小于等于 $k$ 个，且 $\sum \limits_{z \in S}|z|$ 达到最大，则称集合 $S$ 为集合 $I$ 的最长可重区间集。
做法
首先需要了解一个网络流基本模型：一流对多流（可以类比电流），主要用来解决一些可以同时选（可以类比串联）以及不同时选（可以类比并联）。
对于这道题，明显对于两个不相互重叠的集合可以都选，可以用同一个流，而对于两个不重合的集合，则选择就有了限制，需要用两个流。
再将其与模型结合一下，我们可以对于数轴上的点每个点和其后面的点连在一起，流量 $k$，费用 $0$（对应并联），对于每个开区间，其左端点和右端点连在一起，流量 $1$，费用 $len$（对应串联），但由于其中无用的点太多，所以可以离散化一下，最后再将源点 $s$ 和 $1$ 连在一起，将 $cnt$ 和汇点 $t$ 连在一起，跑费用流即可。
Code
最长k可重线段集问题
题意
给定平面上一个个开线段的集合 $I$，和一个数 $k$。有开线段集合 $S\subseteq I$ ,且使得在 $x$ 轴上的任何一点 $p$，$S$ 中与直线 $x=p$ 相交的开线段个数不超过 $k$，且$\sum\limits_{z\in S}|z|$达到最大，则开线段集合 $S$ 称为开线段集合 $I$ 的最长 $k$ 可重线段集。$\sum\limits_{z\in S}|z|$ 称为最长 $k$ 可重线段集的长度。
做法
看似跟 P3358 没什么区别，因为只有一个关于 $x$ 轴的限制，但是因为变成了平面上的线段，所以如果有两条两个端点的横坐标都相等的线段，就不会连到一起，但是不应该这样。
考虑扩域。我们把每个点拆成两个点，如果有左右端点横坐标相同的线段存在，就把右端点的横坐标改为 $2 \times x+1$，理所当然左端点不变为 $2 \times x$。
但问题又来了，扩域之后可能会导致两个本来不交的两个线段交在一起，如何解决？答案是，接着扩域。
我们可以对于一条左右端点的横坐标不相等的点的左端点的横坐标改为 $2 \times x_l+1$，右端点保持不变。
考虑这样做的正确性，很明显对于原先不交的线段 $(a,a)$ 和 $(a,b)$，扩域之后，$(a,a)$ 的右端点变成了 $2 \times a+1$，$(a,b)$ 的左端点变成了 $2 \times a+1$，相对位置保持不变。而对于，两个不交的线段，扩域之后不交还是不交，没有变化。
注意要先扩域再离散化，否则会 T 掉。
Code
太空飞行计划问题
题意
有 $n$ 种实验，$m$ 种仪器，每种实验需要若干种仪器，第 $i$ 台仪器需要 $c_i$ 美元购买，资助方对于第 $i$ 种实验，资助 $p$ 美元，问最多可以挣嫖多少钱。
做法
没什么好说的，建个二分图跑最小割即可。
输出的话，可以直接判断每个点的 $vis$ 是否为空，或者看一眼跟其相连的烦边有没有流即可。
Code
不放了。
魔术球问题
题意
给你 $n$ 根柱子，还有很多球，每个球都有编号，每个球也都可以摆到柱子上，摆放方法为：
若其下方有球，则其下方球的编号与这个球的编号之和为完全平方数
若其下方没球，则随便放
求最多可以摆放的球数，以及一种可行的方案。
做法
一眼最小路径覆盖。
其实就是以这些球为点建图，那么这些球肯定要摆在尽量小的柱子上，即最小路径覆盖。
Code
然后暴力枚举可以摆放的球数即可。
深海机器人问题
题意
给你一个 $p \times q$ 的网格图，以及网格上边的边权，接着给了你 $a$ 个起点和 $b$ 个终点，每个起点有 $k_i$ 个机器人出发，每个终点可以到 $r_i$ 个机器人，每条边的边权只能取一次，且机器人只能往下方和右方走，问机器人走过的路径的最大边权和。
做法
看起来比较麻烦，但实际上硬流就行了，但注意，尽管每条边权只算一次，但是每条边可以走很多次。