洛谷——P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出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);
}