第2回早稲田大学プログラミングコンテスト

E - 独立記念日


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

 長らく続いたW帝国がその歴史に終止符を打とうとしていた.多くの少数部族の反乱により,複数の独立国家に分かれることになったのだ.そこで,帝国のとある領主は次のやっかいな問題に直面している.彼の最後の仕事を手伝ってあげよう.

問題

 N 個の都市を繋ぐ M 個の道路の情報が与えられる.各道路は異なる 2 つの都市を繋いでおり,双方向に移動することができる.道路の情報は2つの異なる都市の番号(1N)と分断コストで与えられる.なお,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} ≦ Nf_{i} ≠ t_{i}1 ≦ c_{i} ≦ 1,000,000 を満たす.
  • 2 つの都市を結ぶ道路の数は高々 1 つである.都市から 1 本も道路が出ていないこともある.
  • 与えられるグラフに含まれる閉路の数は高々 1 つである.

出力

分断に必要な最小コストを 1 行に出力せよ.
なお、最後には改行を出力せよ.

部分点

30 点分については,グラフに閉路を含まないことが保証される.

入力例 1

2 1 2
1 2 5

出力例 1

5

入力例 2

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

出力例 2

15
3 つのグループに分けるためには,すべての道路を切断する必要があり,それには 5 + 5 + 5 = 15 のコストがかかる.

入力例 3

3 1 2
1 2 5

出力例 3

0
既に 2 つのグループ(\{1,2\}\{3\})に分かれているため,これ以上道路を切断する必要はない.よって,0 を出力する.

Submit提出する