精進 APC-001-D Forest
こういう考え方が足りなさ過ぎてつらい
頑張らないとね
精進1
理想な考察の仕方を連ねてみるが(あっている保証がない)
要するに何するんですか (What is this?)
森を木にするための最小コストを調べます
答えはどんな形ですか (Answer?)
森にある木をすべて頂点で結んだ形
頂点はどうやって選びますか (How?)
すべての木をつなぐ->木のうち最低一つの頂点は使う
あとは小さい順
何個頂点を選びますか (Time?)
木を構成するにはn - 1の辺が必要
もうm本引いてあるので n - m - 1
引く辺の頂点はかぶってはいけないので
2 * (n - m - 1)個頂点を選べばいい
簡単ですね
はい
木を作って
木の中でもっとも小さいのを取り出して
あとは個数分だけ取り出す
もうすでに木ができているケースがあるので注意
