bzoj 2132: 圈地计划 网络流

一眼就看出了是网络流,感觉xjb搞一搞很可做。然后xjb搞了半天弃疗了。

我们考虑,如果这道题变成相邻的相同有c的收益就简单了。建一个s,连向所有点,流量为a,所有点连向t,流量为b。相邻的点之间连双向流量为c的边,然后就好了。因为当x,y两个点相邻的点属于同侧时,相邻的点的双向流量不用被割。

然而现在这题是相邻的不同有收益。这就很尴尬了。这样子,我们考虑这个二维平面图像国际象棋棋盘一样,黑一块,白一块。那么说白了,我们相邻的边只会存在在黑白之间。我们考虑我们s向黑块连a,黑块向t连b。s向白块连b,白块像黑块连a。那么我们惊奇的发现,此时如果相邻的两块x,y选择不同的颜色,则其中间相连的边不会被割掉,符合这道题的意义。

然后跑最大流就好了。

过了这么久,突然间发现,自己用的dinic模板竟然有问题。。。少了个优化,然后在一些特定形况的图上会慢很多,quq。感谢Dev-XYS的纠错。

建边的时候注意一下,a,b两个点相邻,那么建一条a – b的双向边,双向流量均为c[a] + c[b]。这里搞错了好久的说。

“bzoj 2132: 圈地计划 网络流”的2个回复

发表评论