きままにものづくり

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

SRM640Div1Easy

問題

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

解法

最小全域木に帰着できるので、プリム法を用いて解く。

計算量

O(E log V)
E:辺の数
V:頂点数

コード