前言
貌似并不知道要说什么（？）
网络流写麻了
（一）P3358 最长 k 重区间集问题
题意：给定 n 个左闭右开的区间，从这些区间中选取一些区间，使得数轴上没有任何一个点被超过 k 个区间包含，并使得区间覆盖长度最大。
题意没给 l,r 范围，先离散化。
先找流量和费用。首先有一个【每个区间只能选择一次】的隐性条件限制。可以想到将次数作为流量，显然长度就作为花费。
那么怎么表示选择一个区间呢？我们可以将区间左端点连向右端点，流量为 1，费用该区间的长度。
一点最多选 k 次，那么我们对于数轴上每一个点 i 连向 i+1，容量为 k，费用为 0。
跑一边最大费用最大流即可。
（二）P4014 分配问题
题意：n 个工件分给 n 个工人，第 i 个人做第 j 个工件的效益为 ci,j，求问在一个零件只能匹配一个工人，并且一个工人只能加工一个零件的情况下，效益最大是多少。
显然有一个二分图的模型，把工人放到左边，零件放到右边。中间是若干边。
很套路的，建立一个虚拟源点 s，连向每一个工人，容量为 1，费用为 0，表示一个工人只能匹配一个，没有匹配零件所以没有费用。
同样，建立一个虚拟汇点 t，每一个零件连向汇点，容量为 1，费用为 0。
之后对于第 i 个工人和第 j 个零件连一条容量为 1，费用为 c_{i,j} 的边，表示一个工人和一个零件只能匹配一次，获得的价值为 c_{i,j}。
要使效益最大，最后跑一边最大费用最大流。
（三）P2774 方格取数问题
题意：m\times n 的方格，每个方格有一个数，选取若干的数，使得任意两个选取的数在方格中没有公共边，求最大和。
直接做不好做，考虑假设我们选取的了所有的数，那么现在我们要求最少删掉的代价。
这样就很像最小割了。
我们对于图黑白染色，若 (i+j)\bmod 2=1，则该点为黑，否则为白。
建立虚拟源点 s，和虚拟汇点 t。我们令 s 连向每一个黑点，容量为点权。每一个白点连向 t，容量同样为点权。表示我们删去这个点需要的价值。
我们将每个黑点连向与它四联通的白点，容量为无限大。
根据最大流 = 最小割，跑一遍最大流就行了。
为什么这样做是对的，性感理解一下。但考虑一张 s\to u\to u'\to t 的图，我们跑最大流肯定是在 s\to u 和 u'\to t 这两条边之间取的最小值，因为如果取了最大值就会超过另一条边的容量。这也就是求得删去的数的最小值。边权为 \infty 表示这两个点见只能选择一个，因为最小割肯定不会割掉边权为 \infty 的边。
最后有所有点的总和减去最小割即可。
（四）P4015 运输问题
题意：单位 i 有 a_i 单位的货物，商店 j 有 b_j 的货物需求量，保证 \sum a_i=\sum b_j。第 i 个单位运到第 j 个商店需要花费 c_{i,j} 的代价，求最小和最大费用。
看出这是一个二分图模型，把单位放到左边，商店放到右边。
很显然是个费用流。货物量就是流量，代价就是费用。因为题目中保证 \sum a_i=\sum b_j，所以想到源点流出的流量等于汇点接受的流量。
建立虚拟源点 s 和虚拟汇点 t，s 连向每一个单位，容量为该单位的货物量，费用为 0。每一个商店连向 t，流量为该商店的需求量，费用为 0。
最后对于每一个单位连向每一个商店，容量无限大，费用就是那个代价。
最后跑一次最小费用最大流和一次最大费用最大流即可。
（五）P2762 太空飞行计划问题
题意：有 m 个实验。每个实验只能进行一次，但会获得相应的奖金，有 n 个仪器，每个实验都需要一定的仪器，每个仪器可以应用于多个实验，但需要一定的价值，问奖金与代价的差的最大值是多少？输出方案。
我们假设选择了所有实验，但所有的仪器先不选，然后找到一个花费最小的方案去掉若干个实验。
这就像最小割了。跟方格取数问题一样。
我们建立虚拟源点 s 和虚拟汇点 t，然后 s 连向每一个实验，流量为奖金，每一个零件连向 t，容量为花费。
求最小割，就相当于跑最大流。
怎么解释这件事情。考虑我们一开始求得奖金总和，假设我们割掉了某一个仪器，那么就相当于这个仪器不选，恰好减去他的奖金。如果割掉了某个零件，就相当于选了这个零件，同样花费了它的代价。
至于输出方案，有一个结论，在最后一次 \text{Dinic} 中，被分到层上点都不会被割掉。
性感证明一下：我们在选择从 s 到仪器的边中，最后一次肯定会选择满流的点，而那些没有满流的点都是被割掉的。然后会对那些满流的节点分层，最后只需判断一下一个点是否分了层即可。
（六）P2770 航空路线问题
题意：从西到东有 n 个城市，m 个航线，每个航线单向连接两个城市。求从最西的城市到最东的城市再回最西城市，除最西和最东城市每个城市只经过一次情况下，经过城市数最多，并输出方案。
首先可以得出一些性质：考虑来回一趟的旅程就相当于从起点到终点两趟，两次不经过相同的城市。【每一个城市只能遍历一次】的条件说明每一条航线也只能遍历一次。
【每一个城市只能经过一次】这一限制条件很套路，将每一个城市拆成两个点，一个入点 u 和一个出点 u'，我们连从 u 到 u' 容量为 1 的边，表示这个点只能经过一次，而题目又要使得经过城市数尽量多，所以可以看出是最大费用最大流的问题，我们让 u 到 u' 的费用为 1，表示经过了一个城市。
之后对于每一条航线，根据一开始推出的每条航线只能经过一次，我们对于每一条航线 (x,y)，从 x' 到 y 连一条容量为 1，费用为 0 的边。
最后跑最大费用最大流即可。
输出方案仍然很简单，网络流有一个性质就是，流量为 0 的边一定是被选上的。那么我们从起点开始 dfs，每一次找边权为 0 的边暴搜下去。然后搜两次，第二次反着输出，因为是返程。
（七）P2754 星际转移问题
题意：有 n 个太空站，容量无限，m 艘飞船，每艘船有容量 h_i，第 i 搜飞船会周期性的停靠太空站，k 个人在地球 0，要使所有人都飞往月球，最快需要多少时间。
考虑按时间分层的 \texttt{trick}。
我们枚举答案 T，那么我们对于每一个船在 T-1 时刻所到达的星球与 T 时刻所到达的星球连一条容量为 h_i，表示最多装 h_i 的人。
当然，上一个时刻的每一个空间的人都可以停留，那么我们将每一个星球上一个时刻和这一个时刻连一条容量为 \infty 的边，表示这个空间站的容量是无限大的。
特殊的，我们建立虚拟源点 s 和虚拟汇点 t，我们将 s 连向地球，容量无限大，月球连向 t，容量也为无限大。
对于每一个时刻都跑最大流，直到最大流不小于 k 为止，说明可以载够 k 个人了。
判断无解考虑并查集即可。
（八）P3254 圆桌问题
题意：m 个单位，第 i 个单位派出了 r_i 个代表。有 n 个桌子，第 i 个桌子可以容纳 c_i 人，要求同一个单位的代表不能做相同桌子，求一个合法方案。
不难看出这也是一个二分图模型，把单位放在左边，桌子放在右边。
我们先建立虚拟源点 s，让 s 连接每一个单位，容量为改单位的代表人数，表示一个单位的初始人数，我们想让这些人都不在同一个餐桌，那么就可以通过流量来起限制作用，我们将每一个单位向每一个餐桌连接一条流量为 1 的边，表示该单位只能对该桌派出一个代表。而餐桌也是有名额限制的，我们将每一个餐桌向虚拟汇点 t 连一条容量为 c_i 的边。
如何判断无解，充要条件是源点的流出量必须等于汇点的接收量。
那么如何判断每一个人都坐在哪些位置呢？还是判断每一条边的流量是否为 0，即可找到每一个人坐到了哪一个餐桌。
（九）P1251 餐巾计划问题
题意：有 n 天，每一天会需要 r_i 个毛巾。可以直接购买新毛巾，或将现有毛巾送到慢洗部或快洗部花一定的钱洗若干天。毛巾用一天就会脏。求最小花费。
我们发现并没有很显然的二分图模型，但发现有【毛巾用一天就会脏】这一条件，提示我们按照【白天】和【黑夜】分层。
我们对于每一天构建两个点，一个黑天一个白天。我们将黑天放左边，白天放右边。
我们知道，每一天的 r_i 个毛巾是必须要满足要求的，那么我们可以把毛巾需求量作为流量。而题目又要使花费最小，不难发现是一道最小费用最大流的问题。
我们建立虚拟源点 s，我们将 s 向每一个黑天连容量为 r_i，费用为 0 的边。表示获取这么多的脏毛巾。
同样，我们建立虚拟汇点 t，我们将每一个白天向 t 连容量为 r_i，费用为 0 的边，表示当天用了这些干净的毛巾。
现在考虑怎样将从源点获取的脏毛巾转变为干净的毛巾。
最直接的是买毛巾。直接从源点获取。向白天连一条容量无限大，费用为每块餐巾的费用。
之后就是快洗和慢洗的问题了，将当天晚上连向洗完那天的白天，容量为无限大，费用为快洗或慢洗的花费。
还有一个小坑，就是当天的脏毛巾可以拖到明天，或是更远几天再洗，那么我们将每一天晚上连向第二天晚上一个容量为无限大费用为 0 的边。
跑一遍最小费用最大流即可。
（十）P2763 试题库问题
题意：有 n 个试题，每个题有若干个 \texttt{tag}，要抽取 m 个道题组成的试卷，类型 i 的试题需要 a_i 个。求一个合法的试卷组合。
这也有一个二分图模型，左边是试题，右边是类型。
由于一个试题只能用一次，那么我们从源点向每一个试题连一个容量为 1 的边。
而当我们选择一个试题之后，就会获得一些 \texttt{tag}，那么我们将每一个试题向它的每一个类型连一条容量为 1 的边，最后每一个类型向汇点 t 连容量为 a_i 的边。表示 i 类型的题需要 a_i。
最后跑一遍最大流。
输出的方法还是一样，找流量为 0 的边就行了。
（十一）P2766 最长不下降子序列问题
题意：给定长度为 n 的数列，求：①最长不下降子序列的长度 s；②每一个元素只能使用一次的情况下，最多可以取出多少个长度为 s 的不下降子序列；③若 a_1 和 a_n 可以使用多次，最多可以取出多少个长度为 s 的不下降子序列。
第一问直接 dp，并记录最长不下降子序列的长度 F 和 dp_i，表示以 i 为结尾的最长不下降子序列的长度。
考虑二三问。
首先发现每个元素只能使用一次，那么套路的，我们对于每一个元素拆点，中间的流量为 1，表示只用一次。
然后枚举 dp 值为 1 的位置，这种位置只能放在开头，那么我们将 s 向它连一条容量为 1 的边。
同理，再枚举 dp 值为 F 的点，这种点只能放在结尾，所以我们将它连向 t，容量为 1。
然后考虑把 s 和 t 关联起来，很容易想到，dp 值其实就相当于一个分层操作，对于两个点 i,j，如果 a_i\ge a_j 且 dp_i=dp_j+1，那么说明 j 可以转移到 i，我们将 j 到 i 连一条容量为 1 的边。
跑一遍最大流就是第二问的答案。
第三问也很简单，我们将 s 到 1 和 1 到它的拆出来的点的流量都改成无穷大。
但是只有在 dp_n=F 的情况下我们才更改 n 到 n 对应的拆出来的点，和拆出来的点到 t 的流量。这是一个小坑。
最大流即可。
（十二）P3355 骑士共存问题
题意：在 n\times n 的棋盘上放置马，使得任意两个马不攻击，有 m 个给定的位置不能放，求最多放几个马。
虽然不能说跟刚刚的方格取数问题一模一样，但也是很类似了。
同样假设取了所有点，然后最小化减少矛盾的马的数量就是最大化答案。
这样对原图黑白染色，然后跑最小割即可。
（十三）P4013 数字梯形问题
题意：给定一个数字梯形，从最顶端开始走 m 条路径，每次朝左下或右下走，三问（一）路径不能相交（二）只能在节点处相交（三）可以在节点或边相交。
我们发现起点有 m 个，是分散的，不如先建立 s 连向第一行的每个数。然后最后一行的每一个点连向 t。容量 1，费用 0。
先考虑第一问，发现又有节点只能经过一次的限制。直接拆点，中间连容量为 1，费用为该节点的权的边。
然后每一个点的出点连向下面一行左边和右边的点，容量为 1，费用为 0。因为边也只能经过一次。
对于第二问，我们直接将每个点的入点和出点的容量改为 \infty，表示每个点可以经过无限次。有一个小坑就是最下面一行的每一个点连向 t 的容量也都改为 \infty，因为某一条路径到达最下面的某一个点后，已经结束了，所以跟到终点的容量没有关系。
对于第三问，除了 s 到第一行每一个点的边以外的所有边的容量都改为 \infty。
然后你就会发现一个特别恶心的事情，对于每一问都得重新建图。
（十四）P2764 最小路径覆盖问题
题意：给定一个 \texttt{DAG}，最少多少条简单路径能覆盖所有点。输出路径。
关于这道题有一个非常巧妙的解法。
首先发现答案的上限是 n，因为每一个点都可以被它直连的一条边覆盖，一共 n 个点，所以答案最多是 n。
然后考虑合并边，每合并两条边答案就减少 1，所以考虑通过最大流来找出边的最大合并数。
这样就很好做了，对于每一个点拆点，然后 s 连向每一个入点，容量 1，每一个出点连向 t，容量 1，之后对于每一条 (x,y)，连 x 到 y' 的一条容量为 1 的边即可。表示合并了两个点。
最后跑一边最大流，答案就是 n 减去最大流。
输出方案采用并查集维护起点，然后对于每一个起点顺着残余网络暴力 dfs 即可。
（十五）P4009 汽车加油行驶问题
题意：给定 n\times n 的方格，坐上 (1,1) 为起点，右下 (N,N) 为终点，X 轴向右为正，Y 轴向下为正，在若干个点上设置了油库可供加油，汽车只能沿着网格边走，遇到加油站必须加油，装满油后最多走 k 条边，初始油量已满。汽车移动时若 X 或 Y 坐标减小，则需花费 B 的费用。加油需要花 A 的费用，可以在某一个没有加油站的点花 C 的费用使油量变满。求最小费用。
这道题很显然是分层图最短路，所以考虑网络瘤。
显然费用流。
我们将图分为 k+1 层，第 0 层表示满油，第 i 层表示用掉了 i 个单位的油。第 k 层就表示油被用光。
我们用三元组 (x,y,z) 表示一个点 (x,y) 的已用油量 z。
建立虚拟源点 s 和虚拟汇点 t。
首先从 s 到 (1,1,0) 连一条流量 1，费用为 0 的边，表示初始油量已满。对于每一个 i 连从 (n,n,i) 到 t 的流量为 1，费用为 0 的边，表示到达终点后车的可能的 k+1 种状态。
之后考虑有加油站的点 (i,j)，汽车会被强制消费。所以 (i,j,z) 连向 (i,j,z+1) 流量 1，费用 A 的边。然后枚举周围点，从状态 0 到状态 1 连边。注意如果横纵坐标减小应该额外花费 b。
然后对于普通点也是同理，只不过连周围点的时候要枚举当前点的状态。
特殊的，若当前点的状态是 k 即油没了，连一条 (i,j,k) 向 (i,j,0) 流量 1 费用 a+c 的边。
（十六）深海机器人问题
题意：有一个 P\times Q 的网格图，左下角为 (0,0)，右上角为 (Q,P)。有 k 个机器人在不同出发地点，有若干目标地点，每个目标地点只能容纳 r_i 个机器人，有些地方有生物标本，每个生物标本有价值，每个生物标本只能被第一个到达它的机器人取走，机器人只能向北或东走，若干机器人可以占据同一位置。求最高价值。
很显然的最大费用最大流了。每个点分别向右边的点连两条边，一条容量 1，费用为该点价值，一条容量无限，费用 0，表示取走一次再不能取。向上同理。
最后把起点和 s 连起来，终点和 t 连起来，容量为机器人数目，费用为 0。
最后跑最大费用最大流即可。
（十七）最长 k 重线段集问题
题意：给定平面直角坐标系 n 个线段，从这些区间中选取一些线段，使得对于任意一点 p 没有任何一条直线 x=p 与超过 k 个线段，并使得线段长度最大值。
其实是最长 k 重区间集问题的升级版，把区间放到直角坐标系上了。
那么一个很直接的想法就产生了，直接把线段投影到 x 轴上！这样就和最长 k 重区间集问题一模一样了。
但是很遗憾，这个想法是错误的，反例也很简单，假设说两条线段在一条是平行于 y 轴的，投影之后就变成一个点了，导致错误。
那么不难想到把线段的长度都扩大一倍，即将线段 i 的左右端点 x_i,y_i 都扩大一倍变成 (2x_i,2y_i)。
而对于一个左右端点相同的区间，可以将它更改成 (2x_i,2x_i+1)。其它节点也都需要更改成 (2x_i+1,2y_i) 的形式。
（十八）魔术球问题
题意：n 个柱子，依次放入无限个球，球从 1 开始编号。每次只能在某根柱子最上面放球，并且在同一个柱子中，任何两个相邻球的编号之和为完全平方数。输出方案。
我们考虑当前放置的球 i，它有两种可能，一是放到某一根已经有魔术球的柱子上，二是自己放到一个新的桌子上。
我们将球分裂，一个入点，一个出点。
首先我们可以将 s 连向入点，容量为 1，表示放到一个新的柱子上。出点连向 t，容量也为 1，这里很重要，表示我们成功放上了一个球。
然后枚举可以与它构成完全平方数的数 x，将 x 的入点连向它的出点，容量为 1，表示一个匹配关系。
跑最大流，直到最大流大于 n，说明所需的柱子量超过了 n，那么停止。
输出方案找流量为 0 的边，暴力 \texttt{dfs} 即可。
还有亿点细节。
（十九）火星探险问题
题意：给定一张网格图，每个点有三种状态，平坦，障碍或岩石标本。有 n 个探测车在移动中须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。求最多获得的岩石标本数。要求打印移动方向。
一道非常板的网络流了。显然车的数量为流量，石头数为费用。
令 s 向 (1,1) 连流量 n 费用 0 的边，表示初始有 n 辆车。(n,n) 连向 t，容量 \infty，花费 0，表示结束任务。
既然涉及到每个石头只能取一次，那么显然是可以拆点的，拆为 a_{i,j} 和 b_{i,j}。
如果 (i,j) 处有石头，那么可以连 (a_{i,j}) 到 b_{i,j} 的流量 1，费用 1 的边，表示只能有一个车取一个石头。石头也可以被取走，连另连一条流量 \infty 费用 0 的边。
另外还有相邻的点连线，每次都是出点连入点，流量 \infty 然后费用 0。
最后就是最大费用最大流。
输出路径还是暴力 \text{dfs}。
\texttt{The End.by UF}
__EOF__
