yukicoder No.19 ステージの選択
強連結成分は定義しか知りませんが，考えればその界隈のアルゴリズムを知らなくても解ける良い問題でした．
問題： http://yukicoder.me/problems/62
解法： あるステージAがクリアできたらステージBのコスト(難易度)が半分になることをA→Bの有向辺で表現し，グラフにする．配列E(from, to)を作り，from→toに有向辺をたどるパスがあるかどうかを求める(ワーシャルフロイドなど)．このとき，頂点(ステージ)Aと頂点Bが同じ強連結成分に含まれることはE[A][B]=E[B][A]=trueであることと等価である．なるべく合計コストを下げる戦略としては，有向辺が伸びていない強連結成分を全て洗い出し，各成分の中でコストが最小のものがinitialにクリアするべきステージである．なぜなら有向辺が伸びている頂点はその親のステージをクリアすればわざわざ最初にクリアして等倍のコストを支払う必要がないし，同じ強連結成分内であれば，どれか1つのステージをクリアすればその他のステージはコストが半分で済むからである．
アルゴリズムの実装方針としては各強連結成分のminimum costを導出する必要があるので，(多分)強連結成分ごとに処理するのが良いと思います．
線形時間で強連結成分分解できるアルゴリズムがあるらしいので，近いうちに見ておこう． Reference: Kosaraju's algorithm - Wikipedia, the free encyclopedia
