[BZOJ3504][CQOI2014]危桥(最大流)

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3504

分析:很容易想到最大流,但如果S-a1,S-b1,a2-T,b2-T这样跑S-T最大流判断是否是满流的话,那么会出现an中间有一部分流从a1-b2,等量的流从b1-a2,这就不符合题意了,于是本渣弱弱翻了题解……

神犇的题解:先按上述跑一边最大流,再把b2当起点,b1当终点跑最大流,如果两次都满流,那么满足。

下面弱弱证明一下第二次最大流的正确性:

设:

a1->a2=an-x

a1->b2=x

b1->a2=x

b1->b2=bn-x

那么我们将b1,b2反过来后,则一定有

b2->b1=bn-x(没满,还可以流)

a1->a2=an-x(没满,还可以流)

可以看到最后都是差了x的流没有满流,但我们最后第二次是做出了满流,所以一定是还有a1->b1=x(a和b是等效的啦啦=+=)

那么a1既可以给b1流x,也可以给b2流x,又由于道路双向,那么可以把a1->b1的流量改为b2->a1->b1总共x的流量,那么b2->b1不就变成了bn了吗,同理a也是一样的,所以就撸完了……

Orz神题

上一篇:Fiddler 拦截 https 请求


下一篇:CDN缓存不命中排查