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