No.018 D

最小全域木を作る問題である.

費用の合計は, 道を費用でソートして, 短い順に Union-Find でつないでいけば求まる. 部分点はこれで取れるはずである. (部分点のテストケースの場合, 組み合わせは1つしかない) ここでは道をつなげる順序は考えなくてもいい. 最終的に全域木になるので, 求めた最小費用合計となる全域木を高橋くんから順に作成すればいいからである.

組み合わせの数であるが, 同じ費用の道が複数本あるときが問題となる.

Union-Find でつなぐということは, 森と森とをつなぐということである. そこで, 同じ費用の道を処理する直前で, 森を頂点とみなしたグラフを考える. 同じ費用の道を同様につないでいくと, いくつかの連結部分に別れたグラフができるはずである. この連結部分ごとに全域木が何種類できるかが分かれば, 同じ費用の道を使った場合の組み合わせの数が求まる.

全域木の数を求めるには行列木定理を使う. ラプラシアン行列を作成し, この行列の任意の余因子が全域木の数となる. なお, 行列式の計算は法を $10^9+7$ とする剰余環上で行う.