SRM 556 - OldBridges

Problem: given undirected graph G, each edge has capacity 2 or INF, determine if there is a multi-commodity flow:

(S_A → T_A) with flow at least 2C_A
(S_B → T_B) with flow at least 2C_B

做法很簡單, 要求兩次 maxflow
Notation: (u, v, c) = edge from u to v with capacity c

Flow 1: Add edge (S, S_A, 2C_A), (S, S_B, 2C_B), (T_A, T, 2C_A), (T_B, T, 2C_B)
Flow 2: Add edge (S, S_A, 2C_A), (S, T_B, 2C_B), (T_A, T, 2C_A), (S_B, T, 2C_B)

如果 F₁, F₂ 的 S-T maxflow 都至少有 2(C_A+C_B), 就 output Yes, 否則 No
不難看出這是 necessary condition, 但這是 sufficient condition 就很不明顯

首先, 由於所有 capacity 都是雙數, 必存在其中一個 maxflow 所有 edge 的流量都是雙數

Let F_A = (F₁ + F₂) / 2
在 F_A 中, S_A 的流入量為 2C_A, T_A 的流出量為 2C_A; S_B, T_B 的剩流為 0
而且滿足流量限制, 所以滿足第一個 flow
相似地, F_B  = (F₁ - F₂) / 2 滿足第二個 flow

Let F = F_A + F_B
但 F 可能會有些 edge 的流量超出 capacity, 不滿足流量限制
可以證明是不會的
注意要對 flow value 加上 absolute value
因為在 F 中, 可以同時存在 (u, v) 及 (v, u) 的 flow, 而且不像一般 flow, 是不能 cancel out 的

|Flow(e)| = |Flow(F_A(e))| + |Flow(F_B(e))|
= |F₁(e) + F₂(e)| / 2 + |F₁(e) - F₂(e)| / 2
≤ max(|F₁(e)|, |F₂(e)|)
≤ Capacity(e)

原題解: http://apps.topcoder.com/wiki/display/tc/SRM+556