作者：蔡麟松_800 | 来源：互联网 | 2023-05-17 18:46
题目链接https:www.luogu.orgproblemnewshowP1195题目背景小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。有很多云飘在那里，看起来很
题目链接
https://www.luogu.org/problemnew/show/P1195
题目背景
小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。
题目描述
给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。
现在小杉要把所有云朵连成KK个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。
输入输出格式
输入格式：
每组测试数据的
第一行有三个数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,N≤100,M≤1000
输出格式：
对每组数据输出一行，仅有一个整数，表示最小的代价。
如果怎么连都连不出K个棉花糖，请输出'No Answer'。
思路
有一个定理：N个点用N-1条边连接成一个连通块，形成的图形只可能是树，没有别的可能。
那么有如下的关系：
所以我们如果想要连出k棵树，就需要连n-k条边。
题目要求用n朵云连出k个棉花糖。因为每个棉花糖都是连通的，那么每个棉花糖就相当于是一棵树。
就是说要用n个节点连出k棵树。即要用n-k条边连出k棵树。
也就是说要花费连出n-k条边的代价。
既然一定要花费连出n-k条边的代价，那么当然要选择代价最小的边连起来。
所以给每条可以连的边按代价从小到大排个序，然后连n-k条边造k个最小生成树就可以了。
（思路是偷的，代码自己打的，逃！）
代码
#include
#include<string>
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,k;
int sum=0,ans=0;
int pre[1001];
struct bian {
int u,v,w;
} b[10001];
bool comp(bian a,bian b){
return a.w<b.w;
}
int find(int x) {
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=n; i++) pre[i]=i;
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&b[i].u,&b[i].v,&b[i].w);
}
stable_sort(b+1,b+m+1,comp);
for(int i=1; i<=m; i++) {
int fx=find(b[i].u),fy=find(b[i].v);
if(fx!=fy) {
pre[fx]=fy;
sum++;
ans+=b[i].w;
}
if(sum==n-k) {
cout<<ans;
return 0;
}
}
printf("No Answer");
return 0;
}
京公网安备 11010802041100号