BZOJ3158&3275 [双倍经验] Number|千钧一发

这俩是一个题。

拿「千钧一发」说吧,你会发现显然如果对于一个i,如果a_i是偶数的话,他一定满足条件2,反过来如果a_i是奇数的话,他一定满足条件1,很好证明,就不说了。

然后你会发现这样一件事情:二分图

我们考虑补集转化,求最少的必须不选的b_i们,这大概……就是一个最小割。

最小割。怎么建图?源点汇点分别连所有奇数/偶数,边权b_i,然后奇偶之间互相连边,边权\rm{INF}

为什么是\rm{INF}?

因为……呃……表示这条边一定不会被割掉,那我们假设他连接了u \; , \; v两个结点,你需要挑一个,把他和源点或者汇点的边割掉。也就意味着最小割增加了b_u或者b_v的权,也就是不选其中一个。

然后这样就形成了超级复杂的关系网络然后就瞎跑Dinic就可以过了

注意!邻接表要开很大,而且两个题范围不一样!

(但是奇怪的是范围较大的\rm{Number}却跑得快

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据