题目: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神题