题目背景
小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。
题目描述
给你云朵的个数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：
1
说明
厦门一中YMS原创
聂老大 又拿出来考了一遍
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k,tot,MST=,fa[];
#define maxm 10000
struct Edge{
int to,value,from;
bool operator < (const Edge &a ) const{
return value<a.value;
}
}e[maxm*+];
void Add_Edge(int u,int v,int w){
e[++tot].to=v;e[tot].value=w;e[tot].from=u;
}
int Find(int x){
if(x==fa[x])return x;
else return fa[x]=Find(fa[x]);
}
int main()
{ scanf("%d%d%d",&n,&m,&k);
for(int i=,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
Add_Edge(u,v,w);
}
if(n<k){
printf("No Answer\n");
return ;
}
sort(e+,e+tot+);
for(int i=;i<=n+;i++) fa[i]=i;
int cur=;
for(int i=;i;i++){
int v=e[i].to,u=e[i].from;
int rx=Find(u),ry=Find(v);
if(rx!=ry){
cur++;
MST+=e[i].value;
fa[rx]=ry;
}
if(cur == n-k )break;
}
printf("%d",MST);
return ;
}
/*思路 ：取 前K条边 连成一棵最小生成树
其余的单独成树
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,ans,fa[1111];
struct node{
int from;
int to;
int value;
bool operator <(const node &a)const
{
return value<a.value;
}
}Edge[11111];
int find(int x)
{
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int main()
{
cin>>n>>m>>k;
int x,y,l;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>l;
Edge[i].from=x;
Edge[i].to=y;
Edge[i].value=l;
} for(int i=1;i<=n;i++)
fa[i]=i; sort(Edge+1,Edge+m+1); int js=1,h=1;
// js 是当前已用边数
// 此题是个最小生成树问题 需成多棵树
// h 用于记录排好序的边中 用到了第几条
if((k>n)||((n-k)>m))// (n-k)k棵最小生成树 需要的边数 然而只有m条边so~~
{
printf("No Answer\n");
return 0;
}
while(js<=n-k)// 生成一棵树用n-1条边，k棵则需要n-k条边
{ int rx=Edge[h].from;
int ry=Edge[h].to;
int w=Edge[h].value;
int fx=find(rx);int fy=find(ry);
if(fx!=fy)
{
js++;
fa[fx]=fy;
ans+=w;
}
h++;
} printf("%d\n",ans); return 0;
}
思路：见代码中的解释