最小生成树模板题-----P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入格式

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

样例解释：

所以最小生成树的总边权为2+2+3=7

思路：将输入的边(左端点a,右端点b,长度w)全部放入到vector里面，然后按长度从小到大排序，之后遍历vector，使用并查集判断a b端点是否相连，已经相连就跳过，否则就就用(a,b,w)连上。
最后，连到N-1条边的时候，图就已经是连通的了，并且选边是从小到大选的，所以长度之和是最小。
如果选边没有到N-1条边，那么肯定图是不连通的

AC代码兼模板

#include <bits/stdc++.h>

using namespace std;

const int NN = 1e4+;

int N,M;

int fa[NN];

struct node{

    int a,b,w;

    friend bool operator < (node n1,node n2){ //node结构体的排序规则，不想定义cmp，毕竟多写一个函数

        return n1.w < n2.w;

    }

};

vector<node> ve; //存放边的容器 

int find(int x){ //查找祖先

    if(x!=fa[x])

        fa[x] = find(fa[x]);

    return fa[x];

}

void join(int x,int y){ //合并

    int fx = find(x),fy = find(y);

    if(fx!=fy)

        fa[fx] = fy;

}

int main(){

    cin>>N>>M;

    for(int i = ;i<=N;i++) fa[i] = i;

    int a,b,w;

    while(M--){

        scanf("%d%d%d",&a,&b,&w);

        ve.push_back({a,b,w});

    }

    sort(ve.begin(),ve.end());//排序

    long long sum = ; //构图的所有边总长度

    int edges = ; //选边数

    for(auto v:ve){

        if(find(v.a) != find(v.b)){ //如果a点与b点没有联通，就选此边进行合并

            join(v.a,v.b);

            sum+=v.w;

            edges++;

        }

    }

    if(edges >= N-) cout<<sum<<endl;

    else cout<<"orz"<<endl;

    return ;

}

巴特西