自动搬运

查看原文

来自洛谷，原作者为

	SovietPower✨ 因你而起的一泓喜悲 权当年轻 留个纪念

搬运于2025-08-24 21:45:58，当前版本为作者最后更新于2019-01-02 08:04:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

代码就不需要放了。。