ARC 076 D: Built?

http://arc076.contest.atcoder.jp/tasks/arc076_b

解き方

• コストの定義を使って，辺の数をO(N)に削減
• 最小全域木をクラスカルなりプリムなりで求める
  • プリムの場合はpriority_queueを使った実装じゃないと多分間に合わない

ハマった所

• プリム，クラスカルの実装からスタート
  • ライブラリ化した方が良いかも
  • 長くなりすぎるのでそろそろ分割しないといけなそう
• プリムのループ内(最小コストの辺の探索，最小コストの更新の部分)をO(logN)に収める方針を立ててしまった
  • コンテスト内で迷った結果として，よほど特殊な条件でないと筋が悪そう
    • 更新しないといけない頂点が高々1個で，どの頂点か分かるなら，最初にmin_costをソートしておくとO(logN)で収まる？
      • 最小コストの辺は，min_cost[0]で求まるのでO(1)
      • 更新対象を削除したのち，二分探索で挿入場所を決めればO(logN)
  • 最小全域木は辺の数を削っていくのが王道なのかな