题解 P3163 【[CQOI2014]危桥】

SovietPower✨

2019-01-02 08:04:38

Solution

这种题大多是多源多汇跑网络流。往返$a_n/b_n$次可以看做去$a_n/b_n$次,直接把危桥能走的次数看做$1$。 先不考虑别的,直接按原图建模:危桥建双向边容量为$1$,普通桥容量为$INF$;然后源点$S$向$a_1,b_1$分别连容量$a_n,b_n$的边,$a_2,b_2$分别向汇点$T$连容量$a_n/b_n$的边。 这样跑出来的最大流会有两个问题(好多题解都没提问题二?): 一是,$b_2\to T$的$b_n$的一部分流量可能是来自$a_1$的,同理$a_2\to T$的一些流量可能来自$b_1$。 二是,危桥只能走一次,但这样可能会正反走两次。 也就是不能直接判断是否满流来判断是否可行。办法是,交换$b_1,b_2$($S$连$b_2$,$b_1$连$T$),重新建图,再跑最大流。只有两次均满流才一定存在可行方案。 交换$b_1,b_2$后再判断是否满流,如果你觉得问题一显然已经被解决了可以跳过下面这段。 > 如果满流且仍然存在问题一那种情况呢?画个图。 > 假设第一次跑最大流,$a_1\to b_2$的流量为$x$,那么$b_1\to b_2$的流量为$b_n-x$,$b_1\to a_2$的流量也是$x$,$a_1\to a_2$的流量是$a_n-x$。 > 而第二次跑最大流,因为是无向图,$a_1\to a_2$和$b_2\to b_1$的流量可以不变,还是$a_n-x,b_n-x$。那么$a_1\to b_2$和$b_2\to a_1$的流量也都还是$x$。 > 而这两次说明了什么呢,$a_1$可以流到$b_1$ $x$流量,还可以流到$b_2$ $x$流量,同时不影响$a_1$与$a_2$,$b_1$与$b_2$之间的流量。因为是无向图,将$a_1\to b_1$的流量反向,就可以得到$b_1\to b_2$ $x$的流量。$b_1,b_2$之间的流就合法了。 > 同理$a_1,a_2$之间的流也合法。 > 所以如果交换$b_1,b_2$后仍满流,一定不存在问题一那种情况。 对于问题二,~~好多题解都没有写也许是太显然了?~~ > 假如$a_1\to a_2$正向经过了一座危桥,而$b_1\to b_2$反向经过了这座桥,那么交换$b_1,b_2$,以$b_2$为起点后,$a_1\to a_2,b_2\to b_1$两条路径都是正向通过了这条边,就受到了流量的限制。 > 所以如果仍满流,不存在问题二。 所以两遍最大流就可以了。 代码就不需要放了。。