きままにものづくり

日々の気付いたことなんかを書いてます。

2015-01-28から1日間の記事一覧

SRM640Div1Easy

問題 V個の色を持つ頂点と、E個のエッジが与えられる。同じ色の頂点を結ぶには1のコストがかかり、それ以外はコスト無しで貼れる。全ての頂点を用いてツリーを構成するのに必要な最小のコストを求めよ。 解法 最小全域木に帰着できるので、プリム法を用いて…