口袋的天空 - 信息学奥林匹克竞赛

问题 2265. -- 口袋的天空

2265: 口袋的天空

时间限制: 0 Sec 内存限制: 128 MB
提交: 2 解决: 1
[上一题][提交][讨论版][状态][下一题]

给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。
现在小杉要把一些云朵连在一起，做成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

每组测试数据的
第一行有三个数N,M,K(1< =N< =1000,1< =M< =10000,1< =K< =10)
接下来M个数每行三个数X,Y,L，表示X云和Y云可以通过L的代价连在一起。(1< =X,Y< =N,0< =L< 10000)
30%的数据N< =100,M< =1000

对每组数据输出一行，仅有一个整数，表示最小的代价。
如果怎么连都连不出K个棉花糖，请输出'No Answer'。

3 1 2
1 2 1

样例2：
Input:
3 1 1
1 2 1

Output:
No Answer

某人这样理解题目：有n朵云，可以做n个棉花糖。现在需要做k个棉花糖，如果能把多出来的云合并到一起，就算成功。如果不成功，没有答案；如果成功，输出合并最小代价。