OldBridges

作者：陈通

关键词：网络流

试题来源

Topcoder SRM 556 Div1 1000

试题大意

有一个包含$n$个点的图，点的编号分别为$0$到$n-1$。有若干双向边连接两个点，有些边可以经过无限次，有些边最多只能经过（双向）两次。Alice计划从$a1$到$a2$进行$an$次往返旅行（一次往返旅行即从$a1$到$a2$，在从$a2$回到$a1$）。与此同时，Bob也计划从$b1$到$b2$进行$bn$次往返旅行。请问是否存在一种方案，使得同时满足两人的计划。

$4 \leq n \leq 50$，$1 \leq an, bn \leq 50$

算法介绍

算法一

可以发现由于所有的边均为双向边，所以对于一次往返旅行，可以拆成2条$a1$到$a2$的路径。

首先考虑只有一个人（Alice）的情况。可以使用网络流求解。对于可无限经过的边，即在两点建立容量均为正无穷的正向和反向边；对于最多经过两次的边，即在两点建立容量均为$2$的正向和反向边。从$s1$到$s2$求出最大流，判断最大流量与$2 \cdot an$的大小关系。但我们发现直接将两个人独立的可行方案直接叠加，是不能判断两人同时旅行的可行性的。

我们设从$\{a1, b1\}$到$\{a2, b2\}$的最大流（源点分别向$a1$和$b1$连容量为$2 \cdot an$和$2 \cdot bn$的边，$a2$和$b2$向汇点连容量为$2 \cdot an$和$2 \cdot bn$的边）为$F_1$，从$\{a1, b2\}$到$\{a2, b1\}$的最大流为$F_2$。由于每条边的容量$c(e)$均为偶数（或正无穷），可知最大流中每一条边的流量$f(e)$均为偶数。令$F_a = \frac{F_1 + F_2}{2}$，$F_b = \frac{F_1 - F_2}{2}$（两个网络流的叠加即将每条边的流量叠加）。可知$F_a$为从$a1$到$a2$的最大流，$F_b$为从$b1$到$b2$的最大流。

易知，若存在可行方案，$F_1$的流量与$F_2$的流量均等于$2 \cdot (an + bn)$。而若$F_1$的流量与$F_2$的流量均等于$2 \cdot (an + bn)$，对于每一条边$e$，$F_a(e) + F_b(e) = |\frac{F_1(e) + F_2(e)}{2}| + |\frac{F_1(e) - F_2(e)}{2}| = \max\{F_1(e), F_2(e)\} \leq c(e)$。$F_a + F_b$即为可行的方案。

所以$F_1$的流量与$F_2$的流量均大于等于$2 \cdot (an + bn)$，为存在可行方案的充分必要条件。