クラスカル法の実装 C編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

1, ..., n の番号のついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。

m 本の重み付き枝が与えられます。クラスカル法を利用して、最小全域木を求めてください。最小全域木とは、全域木のうち、枝の重みの総和が最小のもののことです。

クラスカル法は以下のようなアルゴリズムです。

求めたい枝集合 T := ∅ として初期化する
m 本の枝を重みが小さい順に e_1, ..., e_m とする
それぞれの枝 e_i について(1 ≦ i ≦ m)
  e_i を T に追加したときに、T に閉路ができないならば T に e_i を追加する

アルゴリズムが終了した後、T は最小全域木となります。

入力される値

n m
a_1 b_1 c_i
...
a_m b_m c_m

・ 1 行目に、頂点の個数を表す n と枝の本数を表す m が与えられます。
・ i + 1 行目に、枝 i を表す整数の組 (a_i, b_i, c_i) が与えられます。a_i と b_i は枝 i が結ぶ頂点を表しており、c_i は枝 i の重みを表しています。(1 ≦ i ≦ m)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 n 行出力してください。1 行目に最小全域木の重み（最小全域木を構成する枝の重みの総和）を出力してください。1 + i 行目に最小全域木を構成する枝を表す i 番目の頂点の組を半角スペース区切りで出力してください。

なお、重みが最小で、出力された枝が全域木を構成するものすべてを正答とします。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 100
・ n-1 ≦ m ≦ n(n-1) / 2
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ m)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・ 1 ≦ c_i ≦ 50 (1 ≦ i ≦ m)
・同じ頂点の組は 2 回以上入力されない
・最小全域木が存在することが保証される

入力例1: 4 6
1 2 1
1 3 50
1 4 50
2 3 1
2 4 1
3 4 50

出力例1: 3
1 2
2 3
2 4

入力例2: 6 11
1 2 9
1 6 19
2 6 9
2 5 49
2 4 7
4 6 40
3 6 17
2 3 35
3 4 46
1 3 39
3 5 10

出力例2: 52
2 4
1 2
2 6
3 5
3 6

問題一覧へ戻る