Saiko~ No Contesuto #02 Waiwai Otaku Panic

2015/11/01 (Sun) Hackerrank 最小費用流

問題

問題文

方針

最小費用流で解きました．入力で与えられるグラフの辺は全て費用 $1$，容量 $1$ であるとし， 頂点 $1$ から $v$ までの距離を $dist(v)$ とします． グラフの外にスーパーソース $S$ を用意し，$dist(v)=d$ の頂点に対し費用 $0$ 容量 $A[v]$ の辺を張ります． $S$ から $0$ に流量 $\sum_{dist[i]=d} A[i]$ を流したときの費用が $\sum_{dist[i]=d} A[i]d$ になっていれば OK です． これを全ての $d$ について確認します．

実装

int main(){
    int n,m;
    while(cin >> n >> m){
        vector<int> a(n);
        rep(i,n-1){
            cin >> a[i+1];
        }
        PrimalDual g(n+1);
        Graph gg(n);
        rep(i,m){
            int f,t;
            cin >> f >> t;
            f--, t--;
            g.add_edge(f,t,1,1); // cap, cost
            g.add_edge(t,f,1,1);
            gg[f].eb(f,t,1);
            gg[t].eb(t,f,1);
        }
        bool ok = true;
        int s = n;
        auto dist = dijkstra(gg,0);
        for(int d = 1; d <= 100; d++){
            PrimalDual h = g;
            int sum = 0;
            int cnt = 0;
            rep(i,n){
                if(dist[i] == d){
                    h.add_edge(s, i, a[i], 0);
                    sum += a[i];
                    cnt++;
                }
            }
            if(sum == 0 || cnt == 0) continue;
            int cost = h.solve(s, 0, sum);
            if(cost == -1) ok = false;
            else if(cost != sum*d) ok = false;
            if(!ok) break;
        }
        puts(ok ? "NO PANIC" : "PANIC");
    }
}