小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。
给你云朵的个数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‘。
分析：
一眼扫过去,还以为是最小生成树的模板题,交了个模板上去全WA所以这是一道读题题
正解kruskal做法,题目叫求生成K朵棉花糖的最小代价.
由此我们可以发现提示在生成K颗树的最小代价求K颗树我们只需要(N-K)条边那我们记个数如果用kruskal做法就只需要依次加边直到加到(N-K)条边
代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=1e5+100; const int M=N*2; int root[N],n,m,k,ans,keay; struct Edge { int x,y,z; }edges[M]; bool comp(struct Edge a,struct Edge b) { return a.z<b.z; } int find(int x)//并查集(可能我和大家写的不一样) { int y=x; while(y!=root[y]) { y=root[y]; } while(x!=root[x]) { int ap=root[x]; root[x]=y; x=ap; } return x; } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) root[i]=i; for(int i=1;i<=m;i++) cin>>edges[i].x>>edges[i].y>>edges[i].z; sort(edges+1,edges+1+m,comp); for(int i=1;i<=m;i++) { int fx=find(edges[i].x); int fy=find(edges[i].y); if(fx==fy) continue; else { root[fx]=fy; ans+=edges[i].z; keay++; if(keay==n-k)//这里坑点(N-K)条边构成K颗树 { cout<<ans<<endl; return 0; } if(n-k<0)//如果都没有K朵云那么就不可能生成K颗树 { cout<<"No Answer"<<endl; return 0; } } } return 0; }
原文：https://www.cnblogs.com/CCCPKeay/p/9887197.html