<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$个节点副本就好了。

全部评论

相关推荐

像好涩一样好学:这公司我也拿过 基本明确周六加班 工资还凑活 另外下次镜头往上点儿
点赞 评论 收藏
分享
已老实求offer😫:有点像徐坤(没有冒犯的意思哈)
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务