口袋的天空

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数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'。

输入输出样例

输入样例#1：

3 1 2
1 2 1

输出样例#1：

说明

厦门一中YMS原创

思路：快排+并查集

先把边排一下序，又小到大，有意义（不是把同一联通块的点相连）的链接用掉，最后判断一下，输出答案即可。

代码实现：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m,k,ans;
 5 int a,b;
 6 int f[1010];
 7 struct nate{int q,z,v;}e[10010];
 8 int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
 9 int cmp(const nate&a,const nate&b){return a.v<b.v;}
10 int main(){
11     scanf("%d%d%d",&n,&m,&k);
12     for(int i=1;i<=n;i++) f[i]=i;
13     for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].q,&e[i].z,&e[i].v);
14     sort(e+1,e+m+1,cmp);
15     for(int i=1;i<=m;i++){
16         a=find(e[i].q);b=find(e[i].z);
17         if(a!=b&&k<n){f[b]=a;k++;ans+=e[i].v;}
18     }
19     if(n==k) printf("%d
",ans);
20     else printf("No Answer
");
21     return 0;
22 }

这么水的题我竟然M了，我是不是智商出问题了。

题目来源：洛谷