[USACO06FEB] Steady Cow Assignment

首先 O(B^2) 枚举答案。

然后暴力网络流:

源向每个牛棚连边,容量为牛棚容量。

牛向汇连边,容量为 1

然后对应区间的牛棚向牛连边,容量为 1

感觉好sb的题啊。。。我更sb,居然没想到网络流的解法。

 

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}却跑得快

 

网络流学习笔记

2h被逼学会网络流.png

Edmonds-Karp好像不是很难,唯一的难点好像是残量网络中用负权边转流……

参见#1    #2 (质量一般)

  • 板子