kruskal

2019-11-11 04:34:01

字体：大中小

来源：转载

供稿：网友

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;}

上一篇：BZOJ 1007, 水平可见直线

下一篇：HashCode见解