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 便可以了 (一定會走到)