mini-notes

競技プログラミングの解法メモを残していきます。

APC001 D - Forest (600)

問題:D - Forest

解答:Submission #10116025 - AtCoder Petrozavodsk Contest 001

メモ:森がnfor個あったとすると、その森を連結にするにはnfor-1個の辺を追加する必要がある。

このとき、2 * nfor - 2個の頂点を選ぶ必要があり、nfor個の頂点は各木で最もa[i]が小さいものを選び、のこりのnfor-2個の頂点は全ての頂点の中からa[i]が小さい順(ただし各木で最もa[i]が小さいのは除く)に選べばよい。

特殊ケース

  • n < 2 * nfor - 2(頂点数が足らず、森を連結にできない)
  • nfor = 1 (全体がすでに連結)