全域木の生成 Ruby編（paizaランク A 相当）

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

問題

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

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

m 本の枝が与えられます。この m 本の枝から構成される無向グラフを G とします。そして、q 本の重み付き枝が与えられます。q 本の重み付き枝の中からいくつかの枝を選び、G に追加してグラフ T を生成することを考えます。T が全域木となるように枝を選ぶとき、考えられる枝の重みの総和の最大値を求めてください。

入力される値

n m q
a_1 b_1
...
a_m b_m
c_1 d_1 e_1
...
c_q d_q e_q

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

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

期待する出力: T が全域木となるように枝を選ぶとき、考えられる枝の重みの総和の最大値を 1 行で出力してください。T が全域木となり得ない場合は、-1 を 1 行で出力してください。

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

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

・入力はすべて整数
・ 2 ≦ n ≦ 100
・ 0 ≦ m ≦ n-2
・ 1 ≦ q ≦ n(n-1) / 2 - m
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ m)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・ 1 ≦ c_j, d_j ≦ n (1 ≦ j ≦ q)
・ c_j ≠ d_j (1 ≦ j ≦ q)
・ 1 ≦ e_j ≦ 50 (1 ≦ j ≦ q)
・同じ頂点の組は 2 回以上入力されない
・グラフ G には閉路は存在しない

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

出力例1: 100

入力例2: 6 0 5
1 2 9
1 6 19
2 6 9
2 5 49
2 4 7

出力例2: -1

問題一覧へ戻る