Kruscal算法+并查集 求解最小生成树

http://ac.jobdu.com/problem.php?pid=1347    孤岛连通工程

刚开始的时候使用qsort排序函数进行排序提交一直都是TLE，后来无意中改为sort排序函数提交就AC了，真是太神奇了。。。

#include<iostream> #include<algorithm> using namespace std; #include<stdio.h>struct Edge {int x;int y;int cost; }edge[10001]; int set[10001];inline int find(int x) //带路径优化的并查集查找算法 {int i,j,r;r=x;while(set[r]!=r) r=set[r];i=x;while(i!=r) {j=set[i];set[i]=r;i=j;}return r; } inline void merge(int x,int y) //优化的并查集归并算法 {int t=find(x);int h=find(y);if(t<h)set[h]=t;elseset[t]=h; }/* int cmp(const void *a,const void *b) {return((*(struct Edge *)a).cost-(*(Edge *)b).cost); } */bool cmp(const Edge& a,const Edge& b) {return a.cost<b.cost; }void init(int n) //初始化并查集，各点为孤立点，分支数为n {for(int i=1;i<=n;i++)set[i]=i; } int kruskal(int n,int m) {int i,num,sum,from,to;//qsort(edge,m,sizeof(edge[0]),cmp);sort(edge,edge+m,cmp);sum=num=0;for(i=0;i<m;i++){from = find(edge[i].x); //判断线段的起始点所在的集合 to = find(edge[i].y); //判断线段的终点所在的集合if(from != to) //如果线段的两个端点所在的集合不一样 {merge(from,to); //合并两个集合sum+=edge[i].cost;num++;}if(num==n-1)break;}if(num<n-1)return -1;elsereturn sum; }int main(void) {int i,n,m,k;while(scanf("%d %d",&n,&m)!=EOF){init(n); //初始化for(i=0;i<m;i++){scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].cost);}k=kruskal(n,m);if(k==-1)printf("no\n");elseprintf("%d\n",k);}return 0; }

 

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的Kruscal算法+并查集 求解最小生成树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。