← 返回题目列表

AtCoder · wupc_05

E. 独立日

中文机器翻译题面 查看原题
 长期存在的W帝国正试图在其历史上划下句点。由于许多少数部族的叛乱,它最终分裂成多个独立国家。在这种情况下,帝国的某位领主正面临以下棘手问题。来帮助他完成最后的工作吧。

問題

 N 连接若干城市 M 提供了若干条道路的信息。每条道路都不同 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 对于点分,保证图中不包含回路。

入力例 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 。 你只需要砍掉