片区划分

题目描述

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

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

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

输入格式

第一行有三个数 $n,m,k$（$1 \le n \le 1000$，$1 \le m \le 10000$，$1 \le k \le 10$）。

接下来 $m$ 行每行三个数 $x,y,l$，表示编号为 $x$ 村到编号为 $y$ 村修路的费用。（$1 \le x,y \le n$，$0 \le l < 10000$）

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

输出格式

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

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

样例输入 #1

3 1 2
1 2 1

样例输出 #1

1

样例解释

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

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

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

数据范围

• $1 \le n \le 1000$，$1 \le m \le 10000$，$1 \le k \le 10$
• $1 \le x,y \le n$，$0 \le l < 10000$
• 保证无重边（$x$ 村到 $y$ 村的道路只有 $1$ 条）

知识点与难度

本题涉及的知识点从属于 图论（并查集 / 最小生成树），难度等级：入门。

测试点分布