首页 > 学院 > 开发设计 > 正文

kruskal

2019-11-11 05:11:17
字体:
来源:转载
供稿:网友

https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P3366

据说kruskal比PRim快 其实kruskal有很多的应用,因为它是建立在并查集上的

#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#include<cstring>#include<string>#define Ll long longusing namespace std;struct cs{ int x,y,z;}a[200001];int father[5001];int n,m,xx,yy,ans;bool cmp(cs a,cs b){ return a.z<b.z;}int getfa(int x){ if(father[x]==x)return x; father[x]=getfa(father[x]); return father[x];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+m+1,cmp); for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++){ xx=getfa(a[i].x); yy=getfa(a[i].y); if(xx==yy)continue; ans+=a[i].z; father[xx]=yy; } cout<<ans;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表