ZZXYY's blog

暑期专题三~

这次内容有点多，所以也不是每道题都写了代码，这里都不贴出来，毕竟有的有代码有的没有有点怪怪的。。。

题目与部分题解来源于BYvoid大神，这里就不打出题目了。

部分原题没有给出数据范围，这里补充一下，以方便各位。

完结撒花~~~

1、飞行员配对方案问题

二分图匹配裸题。。。也没什么必要用网络流的算法，直接匈牙利也可以得到方案。。。

2、太空飞行计划问题（M≤30，N≤45）

与之前做的bzoj的一道题类似，就是没有租用仪器的选择，无视就可以了，那道题的题解看这里。

3、最小路径覆盖问题（N≤120，M≤1000）

题目已经自带题解了。。。答案为N减去最大流。这里试着证明一下。

这里构造的图其实是一个二分图，用匈牙利好像也是可以的，二分图中，每一个左边的顶点只能对应右边的一个顶点，首先一个图的路径覆盖最大为N，在二分图中每连一对点就相当于把这一对点加入同一条路径当中，这样每有一对匹配就会减少一个路径覆盖，而同一个点只能出现在一个路径中也与二分图匹配的定义相同。

4、魔术球问题（N≤55）

好像初一的时候在zoj上见过，貌似还有一个公式可以直接出答案的。。。

解法相当暴力。。。由于答案显然存在单调性，那么顺序枚举答案，对任意的i<j，如果i+j是完全平方数，就对i到j连一条边，那么如果可以放在N个柱子上，就相当于是这个图的最小路径覆盖小于等于N，所以我们只需要顺序枚举答案再做一次最小路径覆盖判断即可。

虽然有单调性可以使用二分查找，但是由于顺序查找每次构图都很方便，而二分查找每次都要重新构图，花费的时间反而可能更多。所以二分查找并不是万能的，要在适当的时候使用。

5、圆桌问题

有印象之前好像做过，在学校oj？不记得了。

建图不算很难，每个单位和每个桌子建一个点，从S连向每一个单位，容量为单位人数，再从每一个桌子连向T，容量为桌子容量，然后每一个单位连向每一个桌子，容量为1，最后如果最大流等于总人数说明可行，否则不行。

6、最长递增子序列问题（N≤500）

打炮弹终极版。。。

先用DP出每一位开始的最长递增子序列，即F[i]，这就可以弄出第一问的答案。

第二问可以先把每个点拆成两个a和b，a到b连一条容量为1的边（控制每个点只用一次），然后对于每一个F[i]=s的点，连一条S到ia的容量为1的边（因为只要长度为s的递增子序列），然后对于每一个F[i]=1的点，连一条ib到S的容量为1的边（因为到这里一个递增子序列结束了），接下来对于每一对i<j，并且a[i]<a[j]、F[i]-1=F[j]，连一条ib到ja的边（这样可以保证每次找到的递增子序列都是最长的），求最大流就是答案。

第三问在解决了第二问后很简单，只要将第一个点和最后一个点的ab点间的容量改为无限就可以。

7、试题库问题

和圆桌差不多，每个题目和题目类型建一个点，从S连向每一道题，容量为1，从每一种题目类型连向T，容量为需要的题目数量，然后每一道题目连向所有它属于的题目类型，容量为1，求最大流，如果最大流=M，说明有解，否则无解。

8、机器人路径规划问题

这题太神了，好像没人弄得出来。。。先留个坑好了。

9、方格取数问题

一个叫做二分图最大点权独立集问题的东东，定义是在一个二分图中找出一些点，使得这些点之间没有边相连，这些点的权值之和最大。这题可以转化为这种模型。

首先把整个矩阵黑白间隔染色，然后从S连向每个黑点，容量为这个点的权值，然后从每个白点连向T，容量为这个点的权值，最后每个黑点连向所有相邻的白点，容量无限，最后所有点的权值加起来减去最大流就是答案。

最大点权独立集可以转换为最小点权覆盖集问题，最小点权覆盖集刚好与最大点权独立集互补（这个在《最小割模型在信息学竞赛中的应用》作者胡伯涛里有证明），它的定义是在一个二分图中找出一些点，使得这些点覆盖所有的边，这些点的权值之和最小。而这和最小割很像，首先我们建图就保证最小割不会割掉中间的边，那么如果选出的点中不覆盖所有的边，那肯定在没有选出的点中存在一条S到T的路径，所以只要找到最小割，就能知道最小点权覆盖集，从而得到最大点权独立集。

10、餐巾计划问题（N≤1000）

之前在学校做过了。。。

把每天拆成两个点a和b，S到第一天的a点连一条容量无限，费用餐巾单价的边，每天的a点向b点连一条容量为当天餐巾需求，费用为0的边，每天的b点向“快洗部天数后的那一天”的a点连一条容量无限，费用为快洗部费用的边，慢洗部一样，然后每一天的b点向T连一条容量无限，费用为0的边，最小费用最大流就是答案。

上面建图貌似有点错误，开学去看下AC代码。。。

建图不算很难就不证明了~明明是懒吧喂

11、航空路线问题（N≤30，M≤200）

怎么感觉好像之前见过和这题一样的。。。

将每个城市拆成两个点a和b，每个点的a向b连一条容量为1（限定每个地方只去一次），费用为-1的边，每对连接的城市i和j将其中一个的b点向另一个的a点连一条容量为1（其实容量是多少都无所谓吧。。。），费用为0的边，S连向起点的a，终点的b连向T，容量为1，费用为-1。先计算最大流，如果不是2说明无法找到两条不相交的路线，如果是2最后计算网络的最小费用最大流就可以了，注意这里算到的数值还要取相反数后减去2。

因为题目要求去的城市越多越好，并且每个城市只去一次，所以拆点可以解决后者，两点之间费用为-1可以使最小费用最大流算出最多的城市数，最小费用最大流又以保证最大流为先，所以可以保证得到的最小费用最大流中一定是有两天不相交的路线的。

12、软件补丁问题

题目有点复杂，但理解后不算难懂他要问什么。。。

这题其实奇迹般的并不属于网络流，一共有20个错误，用二进制表示就是只有1048576种可能，我们只要弄出这么多个点，然后在可以使用补丁的点连到使用补丁后的点，边权为使用补丁的时间，那么最短路径就是答案了。

13、星际转移问题

相当于4、魔术球问题+10、餐巾计划问题，顺序枚举需要的天数D，把包括地球和月球在内的所有空间站拆成D个点，从S向每一个地球的点连一条边，容量无限，每一个月球的点向T连一条边，容量无限，再根据太空船的运动连接前一个空间站第D-1个点到后一个空间站第D个点的边，容量为这个太空船容量，如果最大流等于人数，说明D天内可行，否则继续往下枚举。

关于顺序枚举与4、魔术球问题类似，建图的思想与10、餐巾计划问题类似（好吧还是偷懒没有写证明）。

14、孤岛营救问题（N，M，P≤10，K≤150）

自己没有想到，原因是被标题迷惑了。。。说好的网络流24题呢！！！！！！

NMP都在10以内，所以用二进制存储得到钥匙的情况后状态数只有102400种，所以直接BFS就可以了。。。

15、汽车加油行驶问题

噗，怎么又是最短路。。。这堆题目改成图论24题算了。。。

把每个坐标按照油箱的大小拆成K个点，然后建图很好理解，题解写得挺好，我直接照搬过来就可以了。（喂，懒得打字也不要找接口啊）

汽车在地图上点i，剩余油量为l时，对应点为<i,l>。
1、如果油箱不满(l<K)，点i为油库点，从<i,l>到<i.top>建立一条权值为A的有向边。
2、如果油箱不满(l<K)，点i不为油库点，从<i,l>到<i.top>建立一条权值为A+C的有向边。
3、如果油箱不为空，i不为油库点，每层l从<i.l>到<j.l-1>建立一条权值为0的有向边，其中j为i的右边或下边相邻的一个顶点；从<i.l>到<j.l-1>建立一条权值为B的有向边，其中j为i的左边或上边相邻的一个顶点。
4、如果油箱不为空，i为油库点，从<i.K>到<j.K-1>建立一条权值为0的有向边，其中j为i的右边或下边相邻的一个顶点；从<i.K>到<j.K-1>建立一条权值为B的有向边，其中j为i的左边或上边相邻的一个顶点。
求从<(1,1),K>的单源最短路径就是答案了。

16、数字梯形问题

在题目的三个规则上纠结了半天。。。这里简单说一下：

规则一：任意两条路径不能经过同一个数字。

规则二：任意两条路径可以经过同一个数字，但经过一个数字后不能同时经过下一行的同一个数字。

规则三：每条路径不受同时经过的规则约束（每条路径相对独立）。

个人感觉有点像poj3422，只不过那题是在一个矩阵里取数的，但大概做法应该是一样的。

规则一：

每个数字拆成两个点a和b，S向第一行所有数字的a点连一条容量为1，费用为这个数字权值的相反数的边，每个点的a向b连一条容量为1，费用为0的边，每个除了最后一行的数字的b点向下一行相邻数字的a点连一条容量为1，费用为下一行的数字权值的相反数的边，最后一行所有数字的b点向T连一条容量为1，费用为0的边，最小费用最大流的相反数就是答案了。

规则二：

和规则一类似，但因为数字取的次数不受限制，所以就可以不用拆点了，其余的也类似。

规则三：

其实也差不多，在规则二的基础上把除了S连出去的边的容量改为无限就可以，因为没有限制了。虽然我觉得直接DP就可以。。。

17、运输问题（N，M≤100）

不算很难。

每一个仓库和商店建一个点，从S向每一个仓库连一条容量为仓库容量，费用为0的边，从每一个商店向T连一条容量为商店需求，费用为0的边，从每一个仓库向每一个商店连一条容量无限，费用为运输费用的边，最小费用最大流就是第一问的答案，第二问很简单，只要将所有费用取负，求到的最小费用最大流再取回负就可以了。

18、分配问题（N≤50）

我只想知道这和上面那题有什么区别。。。把S连出和连入T的边容量改为1就一样了。。。

19、负载平衡问题

首先容易证明，一个原本存储大于平均值的仓库不需要搬入货物，同理原本存储小于平均值的仓库不需要移出货物。

如果一个仓库的存储小于平均值，就把它设为a类点，如果大于就设为b类，从S向每个a类点连一条容量为仓库存储与平均值差值，费用为0的边，每个b类点向T连一条容量为差值，费用为0的边，每个a类点向b类点连一条容量无限，费用为两点间距离的边，最小费用最大流就是答案。

20、深海机器人问题（P，Q≤15）

也是和poj3422很像，只不过这题是在边上取数的。

解法也比较类似，只是因为这题取得是边上的权值，所以不用拆点，S连向每一个出发点，容量为出发的机器人数量，费用为0，每个点连两条边向东边的和北边的点，一条容量为1，费用为边权值的相反数，另一条容量无限，费用为0，每一个目的地连向T，容量为到达的机器人数量，费用为0，那么最小费用最大流的相反数就是答案。

这种取数且每个数只能取一次的题目大概都是这种解法吧。。。

21、最长k可重区间集问题（N≤500，K≤3）

题目不算难懂，就是没有说明题目里面的z是什么，看完样例大概猜出是每个小开区间的右端点-左端点。

BYvoid大神给了两种解法，但都差不多，我自己想的方法比较接近解法二，但还是有点小问题，这里就讲一下解法二（懒得打解法一就直说嘛）。

将直线上的点离散化，然后从S连向第一个点，容量为K，费用为0，每个点连向下一个点，容量无限，费用为0，每个开区间的左端点连向右端点，容量为1，费用为区间长度的相反数，最后一个点连向T，容量为K，费用为0，最小费用最大流的相反数就是答案。

容量为K的边是为了限定直线上点的重复，左端点向右端点连的边表示使用这个开区间，如果要取这条边就会错过这段区间中其他区间的左端点，而如果还想取那个区间就一定会导致有点的重复产生，所以就要从S来的另一条增广路上过来，正好解决了区间的重复。

22、最长k可重线段集问题（N≤500，K≤15）

上一题的强化版，从一维拓展到了二维。

其实也没有什么差不多的。。。但是上一题的解法二显然就不行了，那种方法建图点数会很大，这里用一下解法一（我才不会说上一题用解法二是因为这一题要用解法一呢）。

将每一条线段拆成两个点a和b，再多弄一个点S‘，从S连向S'，容量为K，费用为0，从S'连向每一条线段的a点，容量为1，费用为0，每条线段的a点向b点连一条边，容量为1，费用为线段长度的相反数，每个b点连向T，容量为1，费用为0，每个线段的b点向编号比它大的并且不相交的线段的a点连一条边，容量为1，费用为0，最小费用最大流的相反数就是答案。

建图理由和上题基本类似。

23、火星探险问题（N，P，Q≤35）

又是这类题目，只是加了个障碍，具体类似16、数字梯形问题（其实更像poj3422），只要把障碍物点的a点和b点之间的边去掉就可以。

24、骑士共存问题

终于到最后一题了。。。

类似于9、方格取数问题，只是每个格子的权值都是1，然后取了一个格子后，不能取的范围变成了骑士的攻击范围而已，注意到棋盘黑白染色后（题目里面就将棋盘染色了），骑士的攻击范围内的格子颜色一定与他当前占据的格子颜色是不同的，所以就像第九题一样了，只是障碍物的那个点无视掉就可以了。

总算是写完了网络流24题的题解，其实有点简单，而且还没有代码。。。做了这么多题目大概也能总结出一点东西，这些题目里面有几题题目的大体模型是类似的，所以解题方法也类似，比如说取数字类型的题目，可以通过拆点解决每个数字只能取一次的问题，还有就是网络流的一些题目中顺序枚举也不失为一种好方法，有时会比二分查找更有效率，对于棋盘的题目，黑白染色往往会有奇效，等等等等。

完结撒花~~~