問題概要

強連結成分の分解を利用する問題。強連結成分を１つの頂点に置き換えて、DAGにして、トポロジカルソートをする。

解法

N個のステージを頂点と考える。(先に指定しておくと良いステージ) -> (ステージ)の向きに有向辺をはっていき、有向グラフを考える。基本的な方針として、難易度の合計が最小になるには、有向グラフの根から葉に向かって、順にステージを選んでいけばいい。つまり、トポロジカルソートした順に辺を選んでいけば、求める解が求まる。しかし、トポロジカルソートをするにあたり、ループがあるのはまずいが今回はサンプル例からもわかるように、強連結成分がが存在する。だから、今回はその部分を求めるために、強連結成分分解を利用した。
強連結成分が存在する場合は場合分けを2つ行う。
(1)強連結成分のみで独立しているまたは強連結成分に対して、入る辺がない場合この場合その成分の中で、難易度が一番小さいものを一番初めに選び、その後他のステージを回れば、他の全てのステージが難易度が半分で回ることができる。
(2)強連結成分に対して、入る辺が存在する場合
この場合、入ってくる辺を強連結成分より先に選んでおけば、強連結成分は全て難易度を半分にすることができる。
これをどのように実装するかは、sccをまず行い、cmp[v] = 頂点vが含まれている連結成分を示す番号となるように、cmpを求める。cmpに入っている番号は連結しているグラフごとに、トポロジカルソートされていて、ループ部分は同じ番号になっている。よって、その数字を利用すれば、トポロジカルソート順に、頂点をめぐることができ、さらに、強連結成分も判別可能なので、その部分では上の場合分けを利用すれば、求めることができる。
実際のケースで図を描いたもの

yukicoder 19 サンプル４

ミス

sccは難しいね。

コード

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

///強連結成分分解 (Kosaraju)///
#define MAX_V 10000//頂点数
int V;
vector<int> G[MAX_V], rG[MAX_V];
vector<int> vs;
bool used[MAX_V];
//cmp[v] = cmp[U]なら、頂点u, vは同じ強連結成分
//cmp[]の値はトポロジカルソートの順番になる
int cmp[MAX_V];//cmp[v] := 頂点vが含まれる連結成分がどれなのかを示す番号
//隣接リストを作る
void add_edge(int from, int to){//0origin
    G[from].push_back(to);//与えられた有向グラフの隣接リスト
    rG[to].push_back(from);//与えられたグラフの矢印を逆した有向グラフの隣接リスト
}
//一度目のdfs
void dfs(int v){
    used[v] = true;
    for (int i = 0; i < G[v].size(); ++i){
        if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);//これ以上進めなくなったものから順にvsに頂点番号を入れていく
}
//2度目のdfs
void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;//頂点vに対して、k番目と強連結成分であること入れる
    for (int i = 0; i < rG[v].size(); ++i){
        if(!used[rG[v][i]]) rdfs(rG[v][i], k);
    }
}
int scc(){
    memset(used, 0, sizeof(used));//0(使ってない)で初期化
    vs.clear();//初期化
    for (int v = 0; v < V; ++v){
        if(!used[v]) dfs(v);
    }
    memset(used, 0 , sizeof(used));
    int k = 0;//強連結成分を分ける番号
    for (int i = vs.size() - 1; i >= 0; --i){//vsに入っている後ろのものからdfs
        if(!used[vs[i]]){
            rdfs(vs[i], k); k++;
        }
    }
    return k;//強連結成分の数
}

int main(void){
    cin >> V;//頂点数n
    vector<int> level(V);
    for (int t = 0; t < V; ++t){
        cin >> level[t];
        int s; cin >> s; s--;//0origin
        if(s == t) continue;//自己ループは使わない
        add_edge(s, t); // s -> t
    }
    int num = scc();//numは強連結成分の個数

    double sum = 0.0;
    for (int k = 0; k < num; ++k){//k番目の連結成分
        vector<int> tmp_level, tmp_node; 
        for (int i = 0; i < V; ++i){//ステージi
            if(cmp[i] == k){//k番目の連結成分の難易度を順に入れていく
                tmp_level.push_back(level[i]);
                tmp_node.push_back(i);
            }
        }
        if(tmp_level.size() == 1){//k番目の強連結成分はサイクルなし
            //この頂点に入ってくる辺がある(向きを逆にしたグラフで判定)
            if(rG[tmp_node[0]].size() > 0) sum += (double)tmp_level[0] / 2.0;
            //この頂点に入ってくる辺がない
            else sum += (double)tmp_level[0];
        }else{//k番目の強連結成分はサイクル有り
            bool flag = false;
            rep(j, tmp_node.size()){//サイクル部分に対して入る辺がある
                if(rG[tmp_node[j]].size() > 2) flag = true;
            }
            if(flag){//全てが1/2
                rep(l, tmp_level.size()){
                    sum += (double)tmp_level[l] / 2.0;
                }
            }else{//難易度が最小のもの以外1/2
                sort(tmp_level.begin(), tmp_level.end());
                rep(l, tmp_level.size()){
                    if(l == 0) sum += (double)tmp_level[l];
                    else sum += (double)tmp_level[l] / 2.0;
                }
            }
        }
    }
    printf("%.1f\n", sum);
    return 0;
}

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.19 ステージの選択

問題概要

解法

ミス

コード