首页 > 代码库 > 克鲁斯卡尔算法求最小生成树
克鲁斯卡尔算法求最小生成树
只是写一个模板，具体讲解就不讲了，是一个并查集的应用+贪心的思想。
路径压缩还是很有用处的，没有压缩的时候tml了三个，压缩之后明变快了不少，虽然还是那么慢
先说一下我的压缩方法就当学习一下并查集：
1 int Find(int x) 2 { 3 int r=x; 4 while(fa[r]!=r)r=fa[r]; 5 while(x!=r){ 6 x=fa[x]; 7 fa[x]=r; 8 } 9 return fa[x];10 }
非递归的路径压缩，先找到祖先结点，然后从头到尾的更新路径的每一个点，让他们直接指向祖先结点
还有一种递归压缩的，代码不是很懂，可以去百度学习一下；
然后是最小生成树代码，用一个结构体存下每一条遍 的值和两个节点，对遍从小到大排序，然后依次判断两个点是否在一个集合了，如果在就操作，如果不在就执行操作，执行N-1就完成了一棵最小生成树
洛谷模板题3366：http://www.luogu.org/problem/show?pid=3366#sub
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<string> 5 using namespace std; 6 #define MAX 200005 7 struct NODE{ 8 int last ,next , val; 9 }node[MAX];10 11 int fa[5005],M,N,ans=0;12 13 int Find(int x)14 {15 int r=x;16 while(fa[r]!=r)r=fa[r];17 while(x!=r){18 x=fa[x];19 fa[x]=r;20 }21 return fa[x];22 }23 24 void work()25 {26 int s=0;27 for(int i=1;i<=M;i++){28 if(s==M-1)break;29 int faa=Find( node[i].last );30 int fbb=Find( node[i].next );31 if( faa !=fbb ){32 fa[faa]=fbb;33 ans+=node[i].val;34 s++;35 }36 }37 }38 39 bool cmp(NODE A , NODE B)40 {41 return A.val<B.val;42 }43 44 void init()45 {46 int i;47 cin>>N>>M;48 for( i=1;i<=M;i++){49 cin>>node[i].last>>node[i].next>>node[i].val;50 }51 sort( node+1 , node+1+M , cmp );52 for( i=1;i<=N;i++){53 fa[i]=i;54 }55 }56 57 int main()58 {59 init();60 work();61 cout<<ans;62 return 0;63 }
克鲁斯卡尔算法求最小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。