题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz输入格式：
第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000） 接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi输出格式：
输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz题解：
自己找资料脑补，毕竟只是个模板。代码：
#include<cstdio> #include <stdlib.h> #include <algorithm> using namespace std; struct arr{ int x,y,z; }a[2000001]; int o,p,n,m,k,tot,ans,f[2000001]; int find(int x){ if (f[x]==x) return f[x]; f[x]=find(f[x]); return f[x]; } bool cmp(arr a,arr b) { return a.z<b.z; } 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+1+m,cmp); for (int i=1;i<=n;i++) f[i]=i; tot=1; k=ans=0; while (tot<n){ k++; o=find(a[k].x); p=find(a[k].y); if (o!=p){ ans+=a[k].z; f[o]=p; tot++; } } printf("%d ",ans); }