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

據(jù)說kruskal比PRim快 其實(shí)kruskal有很多的應(yīng)用，因?yàn)樗墙⒃诓⒉榧系?/p>#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;}