Livedoorブログからの移動
はてなブログからの移動

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)
    • 最小全域木は辺の数を削っていくのが王道なのかな