橋の建設 R(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 国は n 個の島から構成される島国です。今までは島々の行き来は船でのみ可能でしたが、国民の声を聞き入れ、島と島の間に橋を建設して交通の便を向上させることとしました。
島 s と島 t を結ぶ橋の建設コストは c 、そのアクセス指数は a です。アクセス指数とは、その橋の利便性を表す指標で、その値が高いほど利便性が良いものとします。
船でしかたどり着けない島がひとつも存在しないことを第一目標として、建設コストの総和が最も小さくなるように、いくつかの橋を建設することとしました。このとき、考えられる最大のアクセス指数の総和を求めてください。
- 入力される値
-
n
1 2 c_{1,2} a_{1,2}
1 3 c_{1,3} a_{1,3}
...
n-1 n c_{n-1,n} a_{n-1,n}
・ 1 行目に、島の個数を表す n が与えられます。
・ i + 1 行目に橋 i の情報を表す整数の組 (s_i, t_i, c_{s_i,t_i}, a_{s_i,t_i}) が与えられます。s_i と t_i は橋 i が結ぶ島を表しており、c_{s_i,t_i} は橋 i の建設コスト、a_{s_i,t_i} は橋 i のアクセス指数を表しています。(1 ≦ i ≦ n(n-1)/2)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
条件を満たして橋を建設するとき、考えられるアクセス指数の総和の最大値を 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 100
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ n(n-1)/2)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・ 1 ≦ c_{a_i,b_i} ≦ 50 (1 ≦ i ≦ n(n-1)/2)
・ 1 ≦ a_{a_i,b_i} ≦ 50 (1 ≦ i ≦ n(n-1)/2)
・ 同じ島の組は 2 回以上入力されない
- 入力例1
-
4
1 2 24 25
1 3 13 39
1 4 42 8
2 3 3 46
2 4 33 19
3 4 28 23
- 出力例1
-
108
- 入力例2
-
5
1 2 10 50
1 3 20 49
1 4 30 34
1 5 10 33
2 3 20 42
2 4 30 37
2 5 10 43
3 4 20 42
3 5 30 31
4 5 10 43
- 出力例2
-
185
