网络流题目整理/题解

2018-03-27jzqjzq?

最近的网络流作业有点多……
但是有些建图的方法和套路非常吼啊(无论从思路还是技巧方面)
所以开个坑整理一下

题目目录

首先放一下作业列表(按照zhan8855下发列表顺序,分为三个难度等级)

难度1
BZOJ1066
BZOJ1143
BZOJ1458
BZOJ1497
BZOJ1930
BZOJ3171
BZOJ3175
BZOJ3876
BZOJ4554

难度2
BZOJ1001
BZOJ1221
BZOJ1280
BZOJ1305
BZOJ1433
BZOJ1927
BZOJ2132
BZOJ2400
BZOJ2756
BZOJ3698
BZOJ3894
BZOJ3996

难度3
BZOJ1070
BZOJ1189
BZOJ1412
BZOJ2095
BZOJ3504

接下来开始发放题解
声明:所有题解中超级源点记为S,超级汇点记为T

难度1

BZOJ1066 [SCOI2007]蜥蜴

原题链接:BZOJ1066
对于某一石柱,我们考虑裂成入点和出点,入点向出点连流量为高度的边
如果能跳出去,出点连向T,流量无限
如果是初始点,从S流进来流量1的边
然后直接跑即可……

BZOJ1143 [CTSC2008]祭祀river

原题链接:BZOJ1143
显然这首先是DAG,DAG显然是一个二分图……
然后考虑点i能不能到j,这个直接floyd可以解决
接下来的问题就转化成了求最小路径覆盖
答案即为$n-最大匹配数$
直接hungary不虚

BZOJ1458 士兵占领

原题链接:BZOJ1458
无解很好判,现在我们只考虑有解的情况
建三排点,行,点,列
对于第i行,从S流$L_i$的流量到i
对于第i列,向T流$C_i$的流量
对于不是障碍的点$(i,j)$,从行i流过来1的流量,向列j流出去1的流量
跑一遍dinic即为答案

BZOJ1497 [NOI2006]最大获利

原题链接:BZOJ1497
类似此类净获利问题可以想到最小割
对于每个中转站,每个站向T流建立成本
对于每个人,从S向这个人流收益,同时向两个中转站流无限(保证不会被割掉)
然后求一下最小割,得到的值为最少会损失的收益
用总收益减一下即可

BZOJ1930 [Shoi2003]pacman 吃豆豆

原题链接:BZOJ1930
显然发现路线不相交这个条件没有用
考虑暴力建图
对于每个点裂点成入点和出点,入点向出点流1的流量
因为最多只能满流2个流量,所以考虑再建小源点和小汇点(其实小汇点可以不用建)
S向小源点流2(限制两条)
小源点向所有点的入点流1,然后点与点之间如果满足二元LIS条件连边
跑费用流即可
然后发现过不去……
考虑把一些点缩起来
例如对于i,j,k,i能到j,j能到k,i一定能到k
然后考虑i流到k的那条边是多余的,直接接到i->j->k上即可
这样就可以通过了

BZOJ3171 [Tjoi2013]循环格

原题链接:BZOJ3171
题目要求改完后的图由几个环组成
那对于每一个点,显然入度为1,出度为1
所以考虑裂成入点和出点,从S向每个入点流1,每个出点向T流1
相邻点间如果直接箭头可达流量为1,费用为0
否则流量为1,费用为1
问题转化成在满流情况下的最小费用

BZOJ3175 [Tjoi2013]攻击装置

原题链接:BZOJ3175
一个十分简单的二分图最大独立集……

BZOJ3876 [Ahoi2014&Jsoi2014]支线剧情

原题链接:BZOJ3876
每条边设下界流量1,上界流量inf,费用为花费时间
然后跑有源汇最小费用可行流即可……
推荐一篇dalao的blog:有上下界的网络流 学习笔记 By zyf2000

BZOJ4554 [Tjoi2016&Heoi2016]游戏

原题链接:BZOJ4554
我们把某行连续一段可炸到区间看成一个点,列上同理
对于某个点,如果可以放下炸弹,那么该点所在位置的行点和列点连边
跑一波最大匹配就是答案啦

难度2

BZOJ1001 [BeiJing2006]狼抓兔子

原题链接:BZOJ1001
我是不会和你说直接跑dinic可以过的
考虑这个图的最小割等于在对偶图跑个最短路
完了

BZOJ1221 [HNOI2001] 软件开发

原题链接:BZOJ1221
此题同线性规划与网络流24题——餐巾计划问题
套用我之前的题解(餐巾计划问题)

首先可以发现这是一个最小费用最大流问题
建图比较麻烦。。。我们把图看成一个餐巾的清洗关系循环图
首先要保证每一天有一定数量的餐巾能够使用,我们设源点s,汇点t
首先是餐巾的购买问题
然后把每一天i拆成没洗过的点和洗过的点,首先从s向每天的洗过的点连边(流INF费p(买一块的钱))
对于每天需要的餐巾,我们从每天的洗过的点向t连边(流a[i](每天需要的块数,下同)费0),然后再从s向每天的没洗过的点连边(流a[i]费0)
这样就形成了餐巾的重复利用循环。。。(可以这么解释吧……也就是说餐巾被用过之后再重新流通到清洗关系循环中)
或者更直观的解释是:餐巾从某一天的洗过的点流到汇点t被使用者使用后这些餐巾被又扔到源点s,然后流通到了这一天的没洗过的点
(应该都明白了吧 = =
最后就是关于清洗的事情了
a和b都一样的,我们直接从第i天的没洗过的点向第i+a(b)天的洗过的点连边(流INF费fa(fb))
还有一种情况,(没)洗干净的餐巾可以留到下一天使用(清洗),所以再从第i天的(没)洗过的点向第i+1天的(没)洗过的点连边(流INF费0)

为什么这样是对的呢?
首先因为对于所有的没洗过的点连向洗过的点,只有清洗这种途径(购买是从源点s),所以不存在同一天从没洗过的点向洗过的点连边这种事情,这样可以保证循环过程中连边不出现差错。。。
第二,这张图的最大流是已知的了,即所有n天的需要块数之和,所以在这个基础上跑出来的最小费用就是答案了,而这张图设计之巧妙刚好可以满足这个条件

BZOJ1280 Emmy卖猪pigs

原题链接:BZOJ1280
对于每个人,向T流购买数目
然后考虑之前打开过的猪圈的猪可以任意流通
所以如果在第i个人打开的猪圈中第j个人已经打开过($i>j$)
那么第j个人购买之后剩下的都可以流过来用
如果没有打开过,从S向这个点流这个猪圈有的猪的数目
然后直接跑即可

BZOJ1305 [CQOI2009]dance跳舞

原题链接:BZOJ1305
之前在Luogu上用贪心水过去了
考虑对每个人裂成喜欢和不喜欢两个点
对于两人互相喜欢,两个喜欢的点连边
对于两人不喜欢,两个不喜欢的点连边
对于某个人,从喜欢点向不喜欢点流k(限制最多与k个不喜欢的人跳舞)
然后我们考虑二分答案
对于二分出来的舞曲数x,我们从S向每个男生喜欢点流x,每个女生喜欢点向T流x
判断是否满流即可

BZOJ1433 [ZJOI2009]假期的宿舍

原题链接:BZOJ1433
我们首先把人和床分开变成二分图
首先在校不回家的学生向自己的床连一条边,
然后所有人向认识的人里面有床的人的床连边
注意回家的学生要忽略
最后每张床连向T,S向每个在学校的人(包括学生和朋友)连边
然后就跑二分图匹配啦

BZOJ1927 [Sdoi2010]星际竞速

原题链接:BZOJ1927
对于每个星球继续考虑裂点
考虑相邻星球,小星球的出点向大星球的入点流,费用为时间
对于每个点,从S向出点流1,费用为0,表示从这个点开始继续走/瞬移
同时从S向入点流1,费用为瞬移代价,表示瞬移到达该点
显然这张图的最大流最小费用即为答案

BZOJ2132 圈地计划

原题链接:BZOJ2132
考虑最小割
对于收益问题考虑最小化损失
假设题目要求相邻点类型相同增加收益
我们对于每个点,从S流向这个点,流量为商业区收益
从这个点流向T,流量为工业区收益
相邻点双向连流量为额外收益的边
考虑这样连边的正确性
相邻点如果类型相同,那么入边(从S流入)或出边(流向T)都被割了,那么额外收益的边就不用被割
如果类型不同,显然图仍旧连通,唯一的方案是割掉额外收益边
于是就满足条件了
现在回到原题,要求相邻点不同类型
那么我们考虑黑白染色,然后白点反过来建边即可

BZOJ2400 Spoj 839 Optimal Marks

原题链接:BZOJ2400
神题
首先求最小边权和比较好思考
因为$xor$对于每个二进制位单独影响,所以考虑分位进行建图
现在点权只剩0和1,考虑最小割
对于0的点,从S流inf,对于1的点,向T流inf
相互有边连接的点我们双向流1
然后跑个最小割就是当前位的答案
然后spoj原题做完了……
现在考虑最小化点权(就是那些没有定权的点)

方法1:

依照hzwer的思路,从汇点向前dfs,把割在T的点权算上
应该是对的

方法2:

这是你没有做过的全新建图!

我们把原来建图的边权放大K倍(k取大一点如1e4)
然后从S向所有点(除T)流1
所以最小边权和为$最小割\div k$,最小点权和为$最小割\mod k$
由于最小割的一些(显然的)性质,会先考虑把大的边割掉,再去割小的边,于是边权和满足
然后小的流量又不会影响大的流量,所以同时求出了两个值!
妙啊

BZOJ2756 [SCOI2012]奇怪的游戏

原题链接:BZOJ2756
我们将图黑白染色,黑点数目记为$Cnt_{black}$,白点数目记为$Cnt_{white}$
然后记黑点数值总和为$Sum_{black}$,白点记为$Sum_{white}$
设最后变成的那个数为$x$,那么一个显然的等式为
$$Cnt_{black}\times x-Sum_{black}=Cnt_{white}\times x-Sum_{white}$$
如果点数是奇数的话,显然是可以把$x$解出来,因为$Cnt_{black}\not=Cnt_{white}$
如果点数是偶数的话,对于合法的$x$,都是可以有解的
然而我们发现对于$x$如果合法,$x+1$显然合法(因为可以两两+1)
满足二分性质,所以二分$x$
现在$x$知道了,我们关心这个$x$合不合法
对于点$(i,j)$,设这个点值为$a_{i,j}$
如果这个点是白点,从S流$x-a_{i,j}$过来,否则向T流$x-a_{i,j}$
然后白点向相邻黑点流inf
判断是否满流即可
这个题稍微有一点卡常(至少对于我来说)……

BZOJ3698 XWW的难题

原题链接:BZOJ3698
尚未AC

BZOJ3894 文理分科

原题链接:BZOJ3894
这个题代表了这一类题的套路……
考虑最小割
建图,图大致长这样……

原点S(最左边点)表示文科点,汇点T(最右边点)表示理科点
考虑每一个普通点(对应图中上下的点),从S流来文科满意值,向T流理科满意值
对于每个点新建一个文科附加点(图中中间靠左的点),一个理科附加点(图中中间靠右的点)
从S向每个文科附加点流该点文科附加值
每个理科附加点向T流该点理科附加值
然后对于附加点能影响到的普通点:
文科附加点向所有影响到的普通点流inf
所有影响到的普通点向理科附加点流inf
根据最小割的性质不难发现这样的正确性

BZOJ3996 [TJOI2015]线性代数

原题链接:BZOJ3996
转化一下发现答案让我们求
$$\sum_{i=1}^{n}\sum_{j=1}^{n}a_ia_jb_{i,j}-\sum_{i=1}^{n}a_ic_i$$
的最大值
然后a又是01矩阵……
转化模型:选择$i$需要代价$c_i$,同时选择$i$和$j$可以获得$b_{i,j}$的收益,求最大收益
最小割经典问题……
对$(i,j)$建点,从S流$b_{i,j}$,然后这个点向$i$和$j$流inf
i和j分别向T流$c_i$,显然答案即为$$\sum_{i=1}^{n}\sum_{j=1}^{n}b_{i,j}-最小割$$

难度3

BZOJ1070 [SCOI2007]修车

原题链接:BZOJ1070
对于每一个修车工拆成n个点,表示修第几辆车
对于每辆车,从S流1费0
对于每位工人的每一个时间段,向T流1费0
每辆车向工人修倒数第i辆节点流1费用为$修车时间\times i$
因为每个工人修倒数第i辆会对后面修的车贡献修这辆车的时间
最后答案即为最大流最小费用

BZOJ1189 [HNOI2007]紧急疏散evacuate

原题链接:BZOJ1189
首先我们预处理出每个空地到每扇门的最短时间
然后我们二分时间time,然后把每扇门拆成time个点
接下来建图:S->每块空地(流1),每扇门的每一个时刻->T(流1)
然后对于每块空地,枚举能够在t时间内到达的门,连边(流1,空地->门(对应的最短时间那个时刻点))
然后等待的问题只要每扇门的某一时刻点向下一时刻点连上就行了(流inf)
然后跑最大流判断是否满流(流为所有人)就好了

BZOJ1412 [ZJOI2009]狼和羊的故事

原题链接:BZOJ1412
我们把狼和羊分开处理,从S向狼窝流inf,从羊圈向T流inf
然后中间点的连边遵循以下条件

  • 邻居是狼不连边
  • 自己是羊不连边
  • 其他所有情况都连一条流量为1的边

然后直接跑最小割就好啦

BZOJ2095 [Poi2010]Bridges

原题链接:BZOJ2095
二分答案
然后相当于判断一个混合图欧拉回路
推荐一篇dalao的blog:混合图的欧拉回路 By commonc

BZOJ3504 [Cqoi2014]危桥

原题链接:BZOJ3504
把往返看作走两次
于是对于普通桥,直接流inf,对于危桥,直接流2(无向图)
这个应该很显然
然后对于a1,b1,从S分别流$2\times a_n$和$2\times b_n$
对于a2,b2,向T分别流对应的,判断满流即可
然而这样会有问题,a1会流到b2
所以我们再跑一次,只不过S连的是a1,b2,T连的是a2,b1
这样就可以啦

总结

有些题尚未AC,将会持续更新
对于一些经典又有趣的建图套路,如果有的话也会更新的吧
总之这类题目很有趣就是了……