B3604 [图论与代数结构 302] 最短树问题_2 题解

· · 题解

B3604 [图论与代数结构 302] 最短树问题_2

这道题是一道裸的求最小生成树，难度普及—。

算法：Kruskal

Kruskal 是一种贪心求最小生成树的算法，非常de好用。

值得注意的是：1 \le n \le 100000,1 \le m \le 300000 ,边权均是 [0,10^9] 中的整数。所以我们需要用到 long long 类型存储答案。

那么这道题就很轻松的通过啦。

My Code： 

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

using namespace std;

#define int long long //注意long long，我在这里被卡了2次

int n,m,fa[300005],ans;
struct node{
    int x,y,z;
}h[300005]; //结构体存图

bool operator < (node x,node y){
    return x.z<y.z;
} //重载运算符，跟手写一个cmp没什么区别

int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
} //并查集

void Kruskal(){
    sort(h+1,h+m+1);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x=get(h[i].x),y=get(h[i].y);
        if(x==y)continue;
        fa[x]=y;
        ans+=h[i].z;
    }
} //贪心法求最小生成树

signed main(){
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%lld %lld %lld",&h[i].x,&h[i].y,&h[i].z); //存图
    Kruskal();
    printf("%lld",ans);
    return 0; //完美结束qwq
}

蒟蒻的第一篇题解，望管理员大大通过。