No.19 ステージの選択

No.19 ステージの選択 - yukicoder

• topological sort すればいいのはすぐ思いついた。sample テストでエラーになって強連結成分分解しないとダメなことに気づいた。
• ライブラリを引っ張ってきてもいいんだけど、そこまでやらなくても解けそうだなーと思ってたら簡単に解く方法があった。(yukicoder : No.19 ステージの選択 - kmjp's blogを参考)
• 問題の性質に気づく力が足りないなぁ。
• cost 更新の判定が cost[mi] > cost[cur] だけで、強連結成分の開始位置によって見つかる mi の位置が変わってしまうという失敗をやらかした。

class SelectStage {
public:
    void solve(void) {
            int N;
            cin>>N;

            // 強連結成分分解して topologcal sort で DAG にして先頭からみていけばよい
            // この問題の場合、ノードから出て行く辺の数は複数あるかもしれないが、
            // 入ってくる辺の数は1本のみ。よって辺を逆にたどれば強連結成分分解ができる。
            // また、強連結成分に入ってくる辺は存在しない。
            // なので dfs で強連結成分とそのコスト最小の辺をみつけるだけでよい。
            vector<int> cost(N,0);
            vector<int> prev(N,0);
            REP(i,N)
            {
                int l,s;
                cin>>l>>s;
                --s;
                cost[i] = 2*l;  // 2 倍しておけば丸めの影響を考えずにすむ
                prev[i] = s;
            }
            vector<bool> vis(N,false);
            int          mi = -1;
            int          start = -1;
            function<bool(int)> dfs = [&](int cur) {
                if (cur == start) // 一周して戻ってきた
                    return true;
                if (vis[cur]) // もどってこなかった
                    return false;
                vis[cur] = true;
                // 強連結成分の内コストが最小のものを更新
                if (cost[mi] > cost[cur] || (cost[mi]==cost[cur] && cur < mi))
                    mi = cur;
                return dfs(prev[cur]);
            };
            // 全点で一周して戻ってくるか確認する
            // O(N^2)
            vector<bool> flag(N,false);
            REP(x,N)
            {
                fill(RANGE(vis), false);
                mi = start = x;
                if (!dfs(prev[x]))
                    continue;
                flag[mi] = true; // 強連結成分のスタートとなる点
            }
            int totalCost = 0;
            REP(x,N)
            {
                if (flag[x])
                    totalCost += cost[x];
                else
                    totalCost += cost[x]/2;
            }
            cout<<fixed<<setprecision(1)<<totalCost*0.5<<endl; // 2 倍した分割る
    }
};