题解 P3163 【[CQOI2014]危桥】

· · 题解

这种题大多是多源多汇跑网络流。往返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两条路径都是正向通过了这条边，就受到了流量的限制。

所以如果仍满流，不存在问题二。

所以两遍最大流就可以了。

代码就不需要放了。。