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

apc001.contest.atcoder.jp

解き方

  • 前提
    • n個の木を連結にするためには、n-1個の辺を追加する必要がある
    • 条件から辺に含まれる頂点は重複しないので、2n-2個の頂点が辺に含まれる
    • 連結にするためには、各木から少なくとも1つは頂点を選ばないといけない
  • 実装
    • 森をn個の木に分割（O(N))し、それぞれでコスト最小の頂点を選ぶ
    • 残った頂点（N-n)個のうちから、コストが小さい順にn-2個選ぶ
    • 上の2つのコストの和が答え（ただし、最初から木になっているケースがコーナーケース）

github.com