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