首页 > 其他 > 详细

洛谷(LG)P1195口袋的天空

时间:2019-03-02 13:24:57      阅读:141      评论:0      收藏:0      [点我收藏+]

就是一道裸题,求的就是有几块生成树,算并查集的时候加一个判断就好了(每合并一次tot++,直到tot==n-k为止,然后输出就好了) 

https://www.luogu.org/problemnew/show/P1195

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,k,f[1005],tot,maxn;
long long ans;
struct ctrl {
int u,v,w;
}p[10005];
int find(int i){return f[i]==i?i:f[i]=find(f[i]);}
bool cmp(ctrl c,ctrl v){return c.w<v.w;}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i) f[i]=i;
for(int i=0;i<m;++i) scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
sort(p,p+m,cmp);
for(int i=0;i<m;++i)
{
int x=find(p[i].u),y=find(p[i].v);
if(x!=y){
tot++;
f[x]=y;
ans+=p[i].w; 
if(tot==n-k)
{
printf("%d\n",ans);
return 0;
}
}

printf("No Answer");
return 0;
}

 

 
 

洛谷(LG)P1195口袋的天空

原文:https://www.cnblogs.com/--nice--/p/10460565.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!