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算法+并查集 求解最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。