【BZOJ3504】危桥

题面

https://www.luogu.org/problemnew/show/P3163

题解

无向图多源多汇问题(存在性的判断)

首先,往返$b_n$次,看做去$2b_n$次,如果把危桥的看成容量为$1$的双向边,就是去$b_n$次。

直接建立超级源和超级汇,

第一次$S$连$a1$、$b1$,$a2$、$b2$连$T$。先跑一边,看看能不能满流。

第二次$S$连$a1$、$b2$,$a2$、$b1$连$T$。先跑一边,看看能不能满流。

如果两次都能满流,则说明有解。

充分性:因为是无向图,所以如果本来有解,把$b1$和$b2$反过来肯定是有解。

必要性:如果只跑第一次,存在两个问题:

一:来自$b1$的流可能会混到$a$中,跑进$a2$,同理,来自$a1$的流可能会混到$b$中,跑进$b2$。

二:危桥只能走一次,但这样可能会正反走两次。

反过来跑,这两个问题都能解决,因为第一个问题揉在一起的流量会反过来,所以最大流一定减少,第二个问题如果第一次正反走两次,那第二次就是正正走两次,就受到限制了。

代码保护。

原文地址:https://www.cnblogs.com/shxnb666/p/11189383.html