HDU 1863(kruskal)

本文主要是介绍HDU 1863(kruskal)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

题目大意：给你n个点，m条边，问你为了让每个城市之间都能联通最少需要多少钱。

题目思路：最小生成树模板题，第一次打最小生成树..kruskal其实挺简单的，简单地说就是不停的加边。同时需要用并查集的相关知识。首先先对并查集需要用到的数组pre进行初始化，即自己是自己的老大。然后输入边，并且根据边权进行排序。然后把最小边权的拉出来，查一下起点的老大和终点的老大，不一样就让起点跟终点混(pre[x]=y)，其主要目的是不成环。其实这题就是从最小边权开始加边，如果成环就不要。最后的时候遍历一边pre，如果正好生成了最小生成树，那应该所有人的老大都是一个数值，即pre[i]==i仅有一次，如果不是的话说明还没成功输出？

以下是代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{int u,v,w;
}a[105];
int pre[105];
int cmp(node a,node b){return a.w<b.w;
}
int Find(int x){return pre[x]==x?x:Find(pre[x]);
}
int main(){int n,m;while(~scanf("%d%d",&n,&m)&&n){for(int i=1;i<=m;i++){pre[i]=i;}for(int i=0;i<n;i++){scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);}sort(a,a+n,cmp);int ans=0;for(int i=0;i<n;i++){int x=Find(a[i].u);int y=Find(a[i].v);if(x!=y){ans+=a[i].w;pre[x]=y;}}int num=0;for(int i=1;i<=m;i++){if(pre[i]==i){num++;}}if(num==1){printf("%d\n",ans);}else{printf("?\n");}}return 0;
}

这篇关于HDU 1863(kruskal)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---