网络流 杂题

发布于 2018-04-12  2.16k 次阅读


这两天在搞一些网络流的杂题,目标就是做一些没见过的模型,提升一下建模的能力。

首先,打了这么久的dinic,自然会觉得它的BFS有点多余,所以就去学了ISAP,大体思想感觉和Dinic差不多,加上gap优化后就跑的飞快了,但是实测当前弧优化在随机数据情况下并不是很优秀。总之如果遇到不涉及动态加边或者其他有特殊性质的图时,基本上ISAP就是最大流的首选算法了。

UPD:Dinic和ISAP在一般的图里理论上界都是O(v^2e)的,但是Dinic在二分图(并不一定是严格的二分图)中能达到O(sqrt(v)e),而ISAP没有这种性质。

另外,对于费用流,我从hzwer的blog里面学到了“zkw费用流”算法,但是和zkw本人写出的版本不同,这个算法并没有使用KM算法,而是沿用了SPFA。它的主要优化之处就是使用了和上述最大流算法相似的“多路增广”,以及spfa时使用SLF优化。性能上大概快40%~50%,同时也支持动态加边或者限制增广的流量等操作,负权边也不用什么特殊处理,可以直接替代原来的SPFA费用流了。

UPD:lc同学写了个简单的性能测试,比较了随机图中三种费用流算法的性能。结论就是zkw-spfa在稀疏图中完爆其余两种算法,稠密图中不如zkw-km但是仍然比spfa优秀。有兴趣的同学可以自行测试

 

 

UOJ#77. A+B Problem

如果不考虑边数的话,直接暴力连边上最小割就好了,但是这样边数最坏是O(n^2)的,显然爆炸。

我们主要需要优化的就是处理“奇怪点”的边数。那么,可以用线段树的思路,每个节点代表一个区间的情况,线段树上的节点由儿子向父亲连一条边就好了。同时,为了处理j<i的限制,我们要弄的其实是主席树,同时要在不同版本之间连边来表示前缀的情况,这样边数就能限制在O(nlogn)了。

建图的细节比较多,而且需要注意一下空节点不能连边。

 

LOJ#2306. 「NOI2017」蔬菜

其实这道题正解不是网络流,但是费用流优化一下好像能有60~80(我裸的spfa只能跑60,一定是写丑了)。

考虑一步一步处理每个限制。首先,假设天数为t,那么可以把每种蔬菜拆成t+1个点(包括第0天),表示第i天开始时的最大数目,这样从原点连出来一串,就能解决蔬菜过期的限制。接着,我们从原点向第0天连两条边,用来考虑第1个蔬菜以及后面的蔬菜的不同价值。最后只剩下每天卖m个的限制了,那么就对每天开一个点,向T连边即可。

这样建图的点数显然是O(nt)的,但是对于NOI考场上来说,用这样的算法已经可以在短时间内拿到较高的暴力分数了,感觉还是很划算的。

 

BZOJ2597 [Wc2007]剪刀石头布

因为直接搞情况比较多,所以我们考虑补集转换。我们可以用任选三元组的方案数减去不构成所需情况的方案数。

而不构成的条件其实是比较简单的,就是三个点中,一个点连向了其他两个点。假设一个点的出度是x,那么它能贡献的不合法点对数就是C(x,2)=x*(x-1)/2。这样,我们最小化的就是不合法点对数之和。给每条不确定的边开两个点,分别连向两个端点表示定向的过程,之后在从两个端点向T连一堆边表示平方费用,然后就做完了。

 

LOJ#2006. 「SCOI2015」小凸玩矩阵

显然可以二分答案,之后就转化为了二分图匹配的问题,非常简单,就不贴代码了。

LOJ#2003. 「SDOI2017」新生舞会

同样非常简单,分数规划直接上,昨天写的是SPFA流,今天换了ZKW,可以比较一下。

#89311 #2003. 「SDOI2017」新生舞会  Accepted 100 5668 ms 972 KiB C++11 / 2.0 K narcissus 2018-04-12 15:28:43
#90246 #2003. 「SDOI2017」新生舞会  Accepted 100 3391 ms 808 KiB C++11 / 2.4 K narcissus 2018-04-13 15:46:02

 

 

LOJ#6045. 「雅礼集训 2017 Day8」价

有n种药和n种原料,每种药都有价值p[i],每种药对应一些原料,选出一些药,使得对应的原料的并集大小等于药的集合大小,且价值和最小。

首先,有必要知道Hall定理:设一个二分图的两个点集分别为X、Y,那么存在完美匹配等价于从x中任选k个点,都对应了Y中的至少k个点。

接着,我们可以考虑用最小割来解决这个问题。先不考虑边权的正负,我们的目的就是最小化价值之和,那么我们可以让价值变成相反数就变成了最大化,直接上最小割的经典套路。为了考虑负边权,我们还需要给边加上一个比较大的数(2e6),这样,从S连向每种药,权值是fix-x,从每种药连向对应的原料,权值是inf,再从每种原料连向T,权值是fix。原图中割掉了一条S连出的边就代表不选择这种药,割掉一条连向T的边就代表选择这种原料。设割掉了x条S连出的边,那么剩下n-x条,也就是选了n-x种药,对应着右侧至少n-x条边被割掉。因为多割一定不优,所以可以保证集合大小相等。

 

LOJ#6033. 「雅礼集训 2017 Day2」棋盘游戏

二分图博弈。

二分图博弈主要可以判断一类博弈问题的必胜/败情况,主要特征是:

1.有两个玩家进行博弈。

2.两位玩家可以到达的状态可以用二分图表示,状态转移可以用二分图上的边表示。

3.游戏不能经过重复状态且无法移动者输。

满足了以上性质,我们就可以利用二分图的匹配的性质来解决问题了。

首先,假设有两个点集X、Y,如果先手处在X匹配点上,且当前点一定出现在所有的最大匹配中,那么X只要沿着匹配边移动到下个位置即可。由于下个位置不能经过重复状态,而且起点在所有最大匹配中,所以Y能到达的下个位置一定是匹配点。这样往复下去,其实就走出了一条交错轨,长度为奇数,所以先手必胜(注意,先后手的定义可能不同,因为有时候把放下去的第一步看作先手,有时候把移动的第一步看作先手)。如果不一定在最大匹配上,那么X走一步走到的一定是匹配点,就变成了Y想要的,所以先手必败。

因此,问题转化为判断每个点是否一定出现在最大匹配中。如果用Dinic做,问题转化为判断每个点是否一定出现在所有最大流中,关于这个问题,下一道题的官方题解给出了多种做法以及证明。在残余网络上DFS一遍,如果S能到i,要么是i不在当前最大流中所以直接到了,要么就是从一个不在最大流的i'走到了j,又走到了i,那么虽然这个i在当前最大流中,但是可以用这条路径直接替代,所以这样是正确的。同样,如果一个点能到T,那么这个点也在最大流中。

实现上,这道题是二分图所以Dinic完爆ISAP。

 

LOJ#536. 「LibreOJ Round #6」花札

上一题关于二分图博弈已经说的很清楚了。

那么这道题主要是优化建边。其实就是把同一类的连到一起就好了。这样做出来的图虽然不是严格的二分图,但是上面的结论仍然适用,因为我们是从最大流的角度解释的。

 

BZOJ2095: [Poi2010]Bridges

可以先二分答案,将问题转化为混合图欧拉回路问题。

混合图欧拉回路问题,主要利用网络流的流量守恒的性质来解决。

我们可以先随便给无向边规定一个方向,由于欧拉回路要求每条边都经过恰好一次,那么如果存在一个点度数为奇数那么一定不合法,所以我们可以利用这个来判断合法性。

之后,假如一个点入度大于出度,我们需要从S补进来(in-out)/2的流量,否则向T流(out-in)/2,作为初始状态。

考虑将一条无向边反向等价于修改度数,那么我们从v到u加一条流量为1的边就好了。

 


一些坑,占位:

LOJ#2042. 「CQOI2016」不同的最小割
UOJ#168. 【UR #11】元旦老人与丛林


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974