首页 > 代码库 > 洛谷P1547 Out of Hay 最小生成树 并查集
洛谷P1547 Out of Hay 最小生成树 并查集
洛谷P1547 Out of Hay
最小生成树
并查集 路径压缩
#include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <iomanip> using namespace std ; const int maxn = 2011,maxm = 10011 ; struct node{ int from,to,val ; }; node e[maxm] ; int n,tot,u,v,m,ans,x,y ; int fa[maxn] ; inline bool cmp(node a,node b) { return a.val < b.val ; } inline int getfather(int x) { if(fa[ x ]==x ) return x ; fa[ x ] = getfather( fa[ x ] ) ; return fa[ x ] ; } int main() { scanf("%d%d",&n,&m) ; for(int i=1;i<=m;i++) scanf("%d%d%d",&e[ i ].from,&e[ i ].to,&e[ i ].val) ; sort(e+1,e+m+1,cmp) ; for(int i=1;i<=n;i++) fa[ i ] = i ; for(int i=1;i<=m;i++) { x = e[ i ].from ; y = e[ i ].to ; u = getfather(x) ; v = getfather(y) ; if(u != v ) { fa[ u ] = v ; tot++ ; ans = e[ i ].val ; if(tot==n-1) break ; } } printf("%d\n",ans) ; return 0 ; }
洛谷P1547 Out of Hay 最小生成树 并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。