AT_wupc_05 独立記念日

[problemUrl]: https://atcoder.jp/contests/wupc2nd/tasks/wupc_05 長らく続いたW帝国がその歴史に終止符を打とうとしていた．多くの少数部族の反乱により，複数の独立国家に分かれることになったのだ．そこで，帝国のとある領主は次のやっかいな問題に直面している．彼の最後の仕事を手伝ってあげよう． $ N $ 個の都市を繋ぐ $ M $ 個の道路の情報が与えられる．各道路は異なる $ 2 $ つの都市を繋いでおり，双方向に移動することができる．道路の情報は2つの異なる都市の番号($ 1 $ ～ $ N $)と分断コストで与えられる．なお，$ 2 $ つの都市を結ぶ道路の数は高々 $ 1 $ つであり，閉路の数も高々 $ 1 $ つである． $ N $ 個の都市を $ K $ 個以上の独立したグループに分解するとき，分解に必要なコストの最小値を求めよ．ここで，ある $ 2 $ つのグループが独立であるとは，お互いのグループに含まれる都市の間に道がないことである． 入力は以下の形式で標準入力から与えられる． > $ N　M　K $ $ f_{1}　t_{1}　c_{1} $ $ f_{2}　t_{2}　c_{2} $ $ ... $ $ f_{M}　t_{M}　c_{M} $ - $ 1 $ 行目に都市の数を表す $ N $($ 1\ ≦\ N\ ≦\ 100 $) と道路の数 $ M $($ 0\ ≦\ M\ ≦\ N*(N-1)/2) $)，および目標のグループ数 $ K $($ 1\ ≦\ K\ ≦\ N $) が半角スペース区切りで与えられる． - $ 2 $ 行目～ $ M+1 $ 行目にはそれぞれ道路の情報，つまり，道路が結ぶ二つの街の番号 $ f_{i} $ と $ t_{i} $，および分断コスト $ c_{i} $ が半角スペース区切りで与えられる． - 各 $ i $ について $ 1\ ≦\ f_{i}\ ≦\ N $ かつ $ 1\ ≦\ t_{i}\ ≦\ N $ ， $ f_{i}\ ≠\ t_{i} $ ， $ 1\ ≦\ c_{i}\ ≦\ 1,000,000 $ を満たす． - $ 2 $ つの都市を結ぶ道路の数は高々 $ 1 $ つである．都市から $ 1 $ 本も道路が出ていないこともある． - 与えられるグラフに含まれる閉路の数は高々 $ 1 $ つである． 分断に必要な最小コストを $ 1 $ 行に出力せよ． なお、最後には改行を出力せよ． $ 30 $ 点分については，グラフに閉路を含まないことが保証される． ```

2 1 2
1 2 5
```

 ```
5
```

 ```
3 3 3
1 2 5
2 3 5
3 1 5
```

 ```
15
```

 ```
3 1 2
1 2 5
```

 ```
0
```
                            

N/A

N/A