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

题目链接

https://www.luogu.org/problemnew/show/P3366

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例：

输出样例：

说明

时空限制：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

解题思路

很显然这是求一个图的最小生成树，有关最小生成树的基础知识不懂的请看我的另一篇博客：https://www.cnblogs.com/yinyuqin/p/10779387.html

在这里，我们讲的是Kruskal算法。

它的优点有哪些？

不需要建图
相对于prim算法更加灵活

主要思路：

首先，将每一条边存入结构体中，然后将边按照权值从小到大排序，然后依次枚举每一条边，若连接的两个端点不连通则加入最小生成树中。这样就保证了先加入的边一定是权值最小的边。

怎样实现这一个过程呢？

我们要用到并查集来维护。用并查集来判断每一条边连的两个端点是否联通，如果不是，就将这两个集合合并起来，这样就快速地构建了最小生成树。

这个题还有一个点就是判断图是否联通，在这里只需要判断最后的最小生成树中是否只有n-1条边即可。因为n个点的树有n-1条边。数据太水，不用判断也能AC！

下面附上代码。

 #include<iostream>

 #include<algorithm>        //sort的头文件

 using namespace std;

 struct edge{            //结构体来存每一条边

     int qidian;

     int zhongdian;

     int zhi;

 }bian[];

 int n,m,cnt,ans,fa[];//cnt记录共有几条边，ans为最小生成树的边权和

 bool cmp(edge a,edge b){ //sort的比较函数（因为是结构体）

     return a.zhi<b.zhi;

 }

 int find(int x){            //并查集找到x的祖先

     if(fa[x]==x) return x;

     return fa[x]=find(fa[x]);//路径压缩

 }

 int main()

 {

 cin>>n>>m;

 for(int i=;i<=n;i++) fa[i]=i;    //并查集：先将每一个点的祖先定为自己

 for(int i=;i<=m;i++){

     cin>>bian[i].qidian>>bian[i].zhongdian>>bian[i].zhi;

 }

 sort(bian+,bian+m+,cmp);    //有小到大排序

 for(int i=;i<=m;i++){

     int p1=bian[i].qidian;

     int p2=bian[i].zhongdian;

     int f1=find(p1);        //分别找到起点和终点的祖先

     int f2=find(p2);

     if(f1!=f2){                //判断起点终点是否联通

         cnt++;                //如果未联通，就将这条边加入最小生成树

         ans+=bian[i].zhi;

         fa[f1]=f2;            //将这两个点连起来

     }

 }

 if(cnt!=n-){            //cnt!=1时这个图不是连通图

     cout<<"orz"<<endl;

     return ;

 }

 cout<<ans;

 return ;

 }

AC代码

秒客网