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

SRM 537

緊接著 COCI 的一場 SRM, 不過 COCI 最有趣的 Q5 又沒有做, 只做了純打字的 Q6
分到了除我以外只有一個紅色的 room, 形勢不錯

275
想不到甚麼很數學的方法做, 見 input 很細, 於是便轉向想較暴力的做法
易見只需考慮 [0, A*B] 內的數字, 把範圍縮至 40000 個
猜想: 如果 Y 的 possible values 是 finite 的, 那麼 Y ≤ 200

接近得到了一個只需試 40000 * 200 次的 algorithm
但還要快速解決以下問題:
Given integers x, y, z, 是否存在 non negative integer i, j 使得 xi + yj = z ?

如果 i, j 可負的話就很簡單
我的做法是使用 egcd 找出任意一組 (i, j), 同時找出最小的 di, dj 使得 (i + di, j - dj) 也是 solution
就可以判斷是否有 non negative integer solution

由於平時少做 number theory, 種種細節寫了很久 (中途還去了做 500)
最後只得 116 分

500
很快便看出應該對每個 bit 獨立地計算 probability, 然後就是很 standard 的 dp 了
在狀態不錯的情況下 10 分鐘內完成

975
只剩下 20 分鐘時開了 975, 第一感覺是和 Euler path 有關 (近來經常遇到)
再看下去很有 flow 的味道, 很快便想到是 circulation
這時只剩下 15 分鐘, 有很多細節未想, 明知不夠時間寫但又沒有其它事做所以還是試著寫
最後當然是不夠時間完成

Challenge Phase
Room 中只有一個人 submit 975, 立即開來看, 明顯不是用 flow 做
但要找出 counter example 又很不確定, 最後很慢地截出了一個 case, Challenge Succeed
整個 phase 只有 3-4 個 challenge attempt, 很平靜地過去了

System Test
275 Failed
一開始還以為 algorithm 出錯, 原來再一次開細 array
不過還是升了 rating, 歸功於那個 challenge

975 Revisited
整個問題可轉化為:
Given a directed muitigraph, find the longest trail such that each edge is visited at least once (and cannot use more than its multiplicity)

如果有一條符合條件的 trail, 接下來只要不斷找 positive augmenting cycle 就可以
但是做 circulation 時, 使用從 Phuket09 中學到的方法可以很優美 + efficient 地解決
在這條題目中, 更可以同時結合 lower bound flow 的方法解決之

Flow model:
Lets A[i][j] be the multiplicity of edge (i, j), add flow arcs:
S → j, capacity = A[i][j], cost = 0
i → T, capacity = A[i][j], cost = 0
j → i, capacity = A[i][j] - 1, cost = 1

然後 SPFA 解決之
(不過應該沒有可能在 contest time solve 到)

Xian 2006 - Gargoyle

雖然是上星期做的題目, 但還是想記錄下來
是 Lower Bound Min Cost Equal Flow

首先, 要找出 equal edge set 流量的 feasible range
根據論文[1], 這個 range 會是連續的, 即是 [0, u] 的 form
但是, 這題有 lower bound 的限制, 所以 range 應該會是 [l, u]

然後就想找 feasible range, 分別對上下界做 binary search
但是, 在做 binary search 時需要知道是大於 upper bound 還是小於 lower bound
一開始完全沒頭緒, 後來觀察到兩種情況下不滿流的邊是不同的, 就解決了這個問題

然後有一點要注意, equal edge set 取最小可行值 不等於 最小費用
再一次根據論文, cost 在 [l, u] 中是一個 convex function
所以可以用 ternary search 去找 min cost


[1] Algorithms for the Simple Equal Flow Problem, Ravindra K. Ahuja, James B. Orlin, Giovanni M. Sechi, Paola Zuddas

ZOJ 2676 Network Wars

Problem statement: Given a undirected graph, each edge has a cost c, select k edges to disconnect vertex 1 and N, the goal is to minimize c/k

直覺是 binary search 答案
對每條edge, 如果 cost[x][y] < mid, 則直接選取
對餘下的 edge 做 flow 搵 min cut

算法不難想到, 比較挑戰的是 handle precision
發現有些位寫

R < 1e-8 WA
R <= 0 AC

後來想到可能是因為做 flow 的部份和用 dfs 搵 cut set 的 handle 方法要一致

係段 code 既邊個位用 epsilon 也要小心處理

Team Training 13/10/2010 - Phuket 2009

Training 時做不到 K, 在 Joe 的指點下現在做到了
是帶cost的lower bound flow

Problem statement:
Given a directed graph, each edge has 2 cost: Patrol cost and Video cost. Each edge must be either patrol or video, the in-degree of patrol road must equals the out-degree of patrol road on each node. Some edges are pre-assigned to be patrol road. At least one road must be patrolled.

看下去很多條件..
入度和出度其實implies patrol edge是一個個的cycle
所以題目其實是要找一些patrol cycle 去 minimize total cost

先假設所有edge都是video, 每條edge的cost便是轉為patrol的費用

第一步是滿足有些edge必定是patrol的條件
用lower bound做circulation
先不用理cost, 找一個任意的feasible flow

第二步處理cost
其實就是不斷在residual network找negative cycle
用bellman-ford做時, 要注意即使第V個iteration update了node x 並不implies node x 是在 negative cycle 中

最後處理at least one edge must be patrolled
即係搵minimum cycle
由於沒有限定cycle length一定要>2, 可以直接用floyd-warshall做


做完這題終於搞清了lower bound flow的一些概念
有Source和Sink的graph如果有cycle做lower bound flow是NP的

ICPC 2691 Evacuation Plan

本身在 poj 的「網絡流專項」見到的
不過 poj 近排的 special judge 成日死 (同一段 code 隊幾次會出現 AC 同 WA.. )..

Problem

given 一個 cost flow 的 graph (沒有 negative cycle), 及給出一個滿流的流方案 , 問這個方案是否已經是 min cost, 如果不是, 給出一個更好的方案 (不用 optimal)

|V| = 200, |E| = 10000

---

Solution

首先重新做一次 min cost flow 一定會超時..
注意到其實不用求出最 optimal 的 solution, 應該有其它方法

細心想, 如果它的方案不是 optimal, 咁應該可以行一些 augmenting path 去「調整」流量及流向
但由 source 出發已經滿流了

於是想到其實題目是找negative cycle
如果在 residual network 中沿著 augmenting path 搵到 negative cycle 即是存在更 optimal 的 solution
而且 negative cycle 上的 path = 要改流量的邊

Implement

由於只要搵到比佢個方案稍為 optimal 的便行, 所以流量有 1 就夠了
因此第一步找出 residual capacity > 0 的 edge

然後找 negative cycle
我用 SPFA 寫, 如果一個 node 被 update >= |V| 次就表示有 negative cycle..
效率比 bellman ford 好多了, worst case 也只是和 bellman ford 一樣

最後就是起返個 negative cycle 出黎..
呢步卡住左一陣!
一開始以為果個被 update >= |V| 次的 node 一定是在 negative cycle 上
不過其實可以係一些 negative cycle 指出去的 node

最後稍加修改, 不斷行 from[x] 直到走到 cycle 上的 node 便可以了 (一定會走到)

TCO 2010 Round 1

250 - 水題

500 - 兩個 register A,B 一開始 set 做 1 , 每次可以做 A = A+B 或 B = A+B, 問要將 A set 做 L (L <= 10^6) 最少 operation 數

1000 - given一個城市, directed graph, 其中一個 vertex 係酒店, 而家俾你 set 一些 tour, 每個 tour 收費 P, set 幾多條 tour 都得, 條件是每個景點 (vertex) 最多只能被一條 tour 所用, 每個 tour 的成本為 edge 的 cost, 求最大 profit  (|V| <= 50)



250 雖然頹, 但精神狀況太差, 又有頹bug, 得返~220

500 USACO 有條少少似, 不過果條唔識做. 打個表出黎睇下都睇唔出 pattern, 於是試下1000

1000 諗左陣, 發現係 max cost flow! 做法大約係拆點, hotel out = source, hotel in = sink, source 連出去之前有條容量無限 cost 為 P 的邊, 然後每 sent 一個 flow 就試下 update current max

諗到後很興奮, 因為睇落去得好少人做1000. bug唔多, 完場前5mins submit



challenging phase 由於500唔識做好難cha人500, 1000大家又都係flow咁

到system test.. 驚見 1000 failed system test 了  =(
就係咁, 跌出rank850之外, 無得出線..



之後搵返, 原來係做SPFA時,  initialize 我 set vis[ ] = -1, 但由於有負cost, 所以有機會做成明明無 path 都想起返條 path 出黎, 搞到 TLE ..

改善: 實現算法時要諗得全面, 尤其係topcoder, 與其貪code短, code得穩陣更重要