TC SRM556 OldBridges

题意

有一个包含(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)

题意

考虑一个人的,直接跑网络流就好了

考虑两个人,跑的时候会出现起点与终点不固定的情况
假设以({a_1,b_1})为起点,({a_2,b_2})为终点,假设(a_1sim b_2(x)),则有(a_1sim a_2(a_n-x),b_1sim a_2(x),b_1sim b_2(b_n-x))

然后有一个结论:将起点换为({a_1,b_2}),终点换为({a_2,b_1}),如果仍然满流则合法

具体的,通过中转点,可以将原来缺失的(x)再找到其他路径补回来

题外话

太傻了,以为能直接跑,还想了半天为什么不对。。

原文地址:https://www.cnblogs.com/Grice/p/12325486.html