c++最小生成树之克鲁斯卡尔

最小生成树有两个算法，一个是prim，一个是kruskarl。prim算法就相当于以点为主，来找最小生成树
而kruskarl算法就是着眼于边了

核心思想

1.将所有边按从小到大排序
2.枚举某一条边，若与边相连的两个点不在同一个集合，就合并这两个点，不然就跳过（此处会用到并查集），不会并查集的话可以看看我以前写的并查集
3.（重点）若边数=点数-1，则最小树成功生成。原理：这其实就是数学，一条边有两条端点，两条边因为共用一个端点，所以是三个端点（如下）

.___.___.

这就是三个点时边的情况

实现

原题
文字稿如下

题目描述

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

输入输出格式

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

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

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

输入输出样例

输入样例#1： 复制
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例#1： 复制
7
说明

时空限制：1000ms,128M

数据规模：

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

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

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

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

我用了一个结构体来存储（也可以用链式前向星）

const int M=200100;
struct node{
    int x;//出发节点
    int y;//到达节点
    int w;//边长度
}a[M];

读入

cin>>n>>e;
    for(int i=1;i<=e;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);

排序

sort(a+1,a+e+1,cmp);

就只有这么一行。
sort其实是algorithm头文件的一个函数，用来排序，后面我会专门有一篇文章来讲它 。
cmp是一个函数，用来排序。

bool cmp(node x,node y){//注意开结构体类型
    if(x.w<y.w)return 1;//如果边 x的长度小于边y的长度，函数返回真，也就是要交换的意思
    if(x.w==y.w)//如果边的长度相同（只是为了判重）
        if(x.x>y.x)return 1;//返回 起点更大的
    return 0;
}

主程序

for(int i=1;i<=e;i++)
{
        if(getfather(a[i].x)!=getfather(a[i].y))
    {//如果点 x与点y不在同一个集合里
            ans+=a[i].w;//把这条边 的长度加入总和
            dad[getfather(a[i].x)]=a[i].y;//并 集过程
            p++;//p记录边的数量
        }
   }//因为题目数据，我就直接遍历了所有边

最后输出

cout<<ans;//输出总和

还是很简单吧？
完整代码：

#include <bits/stdc++.h>
using namespace std;
const int M=200100;
struct node{
    int x;
    int y;
    int w;
}a[M];
int n,e,dad[M],p=1,ans;

bool cmp(node x,node y){
    if(x.w<y.w)return 1;
    if(x.w==y.w)
        if(x.x>y.x)return 1;
    return 0;
}
int getfather(int x){
    if(x==dad[x])return x;
    dad[x]=getfather(dad[x]);
    return dad[x];
}
    
int main()
{
    cin>>n>>e;
    for(int i=1;i<=e;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
    sort(a+1,a+e+1,cmp);
    for(int i=1;i<=n;i++)dad[i]=i;
    for(int i=1;i<=e;i++){
        if(getfather(a[i].x)!=getfather(a[i].y)){
            ans+=a[i].w;
            dad[getfather(a[i].x)]=a[i].y;
            p++;
        }
    }
    cout<<ans;
    return 0;
}