2090 - 片区划分

题目描述

A 市有 n 个村庄(村庄编号为 1 \sim n ),现准备将 n 个村庄划分为 k 个区(一个区中要有至少 1 个村庄),同一个区中的村庄要求有道路可以互相到达(不一定要直达,比如:A 村要去 C 村,可以先先去 B 村,再去 C 村)。

为了节约成本,在划分之前,相关规划部门调研了村庄之间修路的成本,本次调研,共调研到了 m 条道路的建设成本。

假设所有村庄之间目前没有任何道路,如果要将 n 个村庄划分为 k 个区,请求出最少的修路成本?

输入

第一行有三个数n,m,k(1≤n≤1000,1≤m≤10000,1≤k≤10)

接下来m行每行三个数 x,y,l,表示编号为 x 村到编号为 y 村修路的费用。(1≤x,y≤n,0≤l < 10000)

测试数据保证 x 村到 y 村的道路只有 1 条。

输出

输出一个整数,代表最少的修路成本。

如果按照当前的调研数据,无法将 n个村庄划分为 k 个区,请输出No Answer。(比如,假设有 5 个村庄,只有 2 条道路的建设数据,是无法将 5 个村庄划分为 2 个区或者 1 个区的)。

样例

输入

3 1 2
1 2 1

输出

1
说明

样例解释

1 号村到 2 号村修路成本为 1

样例要求将 3 个村划分为 2 个区,只需要修 1 条路就可以将 2 个村合并为 1 个区,加上剩余的 1 个村,形成了 2 个区。

因此,样例中只需要在 1 号村和 2 号村之间修路,就可以实现划分 2 个区的目标。

来源

并查集 图论

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 534
通过人数 270
金币数量 1 枚
难度 入门


上一题 下一题