首页 > 代码库 > Kruskal算法 克鲁斯卡尔
Kruskal算法 克鲁斯卡尔
30行
#include <iostream>#include <algorithm>using namespace std;int f[5001],n,m,ans=0,i,ok;int getf(int x)//递归找爹 { return f[x]==x?x:f[x]=getf(f[x]);}struct edge{ int u,v,w; bool operator<(const edge sb)const { return this->w<sb.w; }}a[200001];int main(){ cin >> n >> m; for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=m;i++) cin >> a[i].u >> a[i].v >> a[i].w; sort(a+1,a+1+m); for(i=1,ok=1;ok<=n-1&&i<=m;i++) if(getf(a[i].u)!=getf(a[i].v)) ans+=a[i].w,f[getf(a[i].u)]=getf(a[i].v),ok++; cout << ans << endl; return 0;}
233
Kruskal算法 克鲁斯卡尔
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。