結果

問題 No.19 ステージの選択
コンテスト
ユーザー codershifth
提出日時 2015-07-20 18:37:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,222 bytes
コンパイル時間 1,719 ms
コンパイル使用メモリ 167,156 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 10:03:17
合計ジャッジ時間 2,415 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

std::vector<int>
topological_sort(const std::vector<std::vector<int>> &tree) {
        int V = tree.size();
        std::vector<int> ord;
        std::vector<bool> vis(V,false);
        std::function<void(int)> visit = [&](int v) {
            if (vis[v]) return;
            vis[v] = true;
            for (auto u : tree[v])
                visit(u);
            ord.push_back(v);
        };
        for(int v = 0; v < V; ++v)
            visit(v);
        std::reverse(ord.begin(), ord.end());
        return std::move(ord);
}

using namespace std;

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 倍した分割る
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new SelectStage();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0