<span>网络流杂题 一</span>
A. 奇怪的游戏
网格图在网络流中往往对应着黑白染色,当然还有四色染色等奇怪的东西。
建图并不难,但是二分的思想是很好的。
考虑如何检验一个答案$x$,将黑点视为二分图的左部点,白点视为二分图的右部点。
一次操作对应一组相邻黑白点$+1$,所以直接建图看能否跑满流就完了。
然而需要注意,显然仅当黑点数=白点数时,答案具有单调性。
然而对于黑点数不等于白点数,答案只可能为一个固定值,只要检查单点就可以了。
B. 士兵占领
对于行列关系的建图,可以分别将行列放在二分图的两侧,行列连边表示行列的交点。
题中的限制为至少,所以可以用上下界最小可行流来解决。
利用本题并没有规定上界,一个更好的解决办法是将至少放置转化为至多放置,
即考虑删掉点的过程,这样可以直接用流量进行最大的限制。
C. 紧急疏散evacuate
似乎是一个常见的套路,将原图中的节点按不同的状态拆分。
在本题中可以表现为每个时间拆点,然后可以直接建边就好了。
本题可以通过二分答案来确定答案的大小,另一个好打的(或许也会更快)做法是直接在残量网络上加点/加边。
D. 狼抓兔子
最小割可过。
当然正解是平面图转对偶图,
将平面图割出的每个块视作对偶图中的一个点,
在块之间建边,边权即分割两个块的边的流量。
这个东西蛮好理解的(尤其是双向边流量相同时),画画图就好了。
E. 切糕
同一行列必须选一个点,所以将点连成一串解决。
相邻两个点的限制为距离不超过$d$。
考虑$inf$边$(a,b)$的作用为$s->a$或$b->t$必须割一个。
所以对于有限制的(即相邻的)每个点对$(i,j)$,从$i$的第$k$个副本,向$j$的第$k-d$个副本连$inf$边就好了。
F. Figure Eight
因为复杂度允许$O(n^3)$,
单调指针维护每个区间对应的最大长度,
然后区间$dp$统计一下就好了,求大神教我网络流做法。
G. 最大获利
选择两个点,对应一个收益。
算是个最简单的最大权闭合子图。
因为收益次数并不多,对每个收益新建一个点,连一些$inf$边就好了。
H. happiness
还是一道最大权闭合子图题,然而两侧对应了不同的选择。
因为收益次数并不多,对每个收益新建一个点,连一些$inf$边就好了。
I. employ人员雇佣
还是一道最大权闭合子图题,然而二者一个选而一个不换会对应一个损失。
这个时候我们可以向$DC$大神学习解方程技巧,通过奇怪的边权来因为收益次数并不多,对每个收益新建一个点,连一些inf边就好了。
因为收益次数很多,对每个收益新建一个点的做法$T$掉了。
这个时候就可以学习大神的技巧,在造成收益的点$(i,j)$之间建边。
具体来说,将每个点分别连$s$,$t$,流量分别为该点造成的收益和,选择该点的花费。
割两个方向分别代表着不选/选。
这样对于$(i,j)$均选,$(i,j)$均不选的收益都是正确的。
对于$(i,j)$只选一个,会导致收益多获得了一份/损失没有统计,所以在$(i,j)$ $(j,i)$之间连边$2*val_{i,j}$就可以统计这一份贡献。
J. 不同的最小割
似乎是一个名为最小割树的数据结构。
算法流程大概是:
初始集合为全部点集。
每次任取集合中的两个点$a$ $b$,跑出二者之间的最小割。
在$a$ $b$之间建边,为最小割的权值。
$S$ $T$一定不联通,将$S$ $T$两个集合分别进行分治就好了。
最终任意两点的割,对应着两点树上的割,即唯一路径的最小边权。
这个玩意就并不会证明,但是结论好背,代码好打。
K. 晨跑
直接拆点限制点的流量,费用流。
L. 80人环游世界
裸的上下界最小费用可行流。
然而做到这里的时候并不会这个优秀的算法。
所以乱搞出了一个奇怪的算法。
给一些边权加上$-inf$,这样在最小费用的前提下一定会流满这条边,然后问题就解决了。
$HErk2$ $kx$大神告诉我,这个做法就很没有拓展性,就很$five$。
然而$cbx$告诉我,对于上下界费用流,只要对下界部分用这个做法,上下界之间的部分用普通流就好了,大神告诉我这个做法就很帅。
因为大神$cbx$>$rk2$,显然$cbx$大神是对的。
M. 修车
刚开始考虑的是正向考虑,即正常人的思维方式,然后这个图就很不可建。
正解的做法是逆向考虑,倒数第$k$辆修的车,只造成了$k$倍修车时间的贡献。
所以将每个修车师傅拆为$n$个点,分别表示修的倒数第$k$辆车就好了。
N. 数字配对
又是一类套路题?
配对问题往往利用一些特殊性质,
划分为二分图的形式,分别连在$s$,$t$上,之间连边就好了。
该题中的划分表现为质因子个数的奇偶性。
O. 美食节
与《修车》一题的建图就比较类似,然而暴力建图必死。
然而本题中拆点的限制就表示,当倒数第$k$辆车还没修时(假设修车=做菜),倒数第$k+1$辆车是没用的。
所以在增广到某师傅修倒数第$k$辆车的节点的时候,新建第$k+1$个节点副本就好了。