2008-09-09 最小根指定有向木 Algorithm 1. 根以外の全ての点について、入ってくる辺のコストの最小値を求め、その値をコストから引く 2. 入ってくる辺がない点が存在したら、有向木は存在しないのでそこで終了 3. コスト0の辺のみからなるグラフ上で強連結成分を計算し、それらを一つにまとめる 4. 新しくできたグラフについて再帰的に計算し、その値に1で求めた最小値の和を加えたのが答え 5. コストだけでなく有向木自体を求めたいなら、強連結成分をまとめた時に各辺のもともとの辺を覚えておけばいい強連結成分の部分除けば20行くらいで書ける例題:http://acm.pku.edu.cn/JudgeOnline/problem?id=3164