B3604[最短树问题_2]题解

· · 题解

此题其实与“最短树问题_1” 几乎一模一样。（除了数据范围）

数据范围比较庞大：1≤n≤100000，1≤m≤300000

而面对这么庞大的数据，当然是要用速度较快的 Kruskal 算法了。

Kruskal 算法求最小生成树

（来源于网络，侵私删）

我们来介绍一下 Kruskal 算法。

Kruskal的方法十分明了，算法过程中要运用到 并查集 不知道的同学可以点进这个链接看一下相关的例题。

我个人认为这个算法比 Prim 算法更加容易懂一些，就是将所有图之间的边权排序，然后从小到大的一个一个连。

会不会你认为这样就完了？不，还要判环。因为要构造的是最小生成树，不能出现环。如果出现了怎么办呢？简单，舍去后继续找就行了，直到连成了总点数减一的点就停止。

边权排序从小取比较简单，但判环就需要用并查集算法来判了。假设对于点 x 与点 y，利用并查集查找这两个点的祖先是否相同。如果相同便有环，不相同则无环。

Kruskal 算法的基本原理也已经明了，上代码！

#include<bits/stdc++.h>
#define ll long long
#define INF INT_MAX
using namespace std;
const int N = 100005;
const int M = 300005;
int ans = 0, sum = 0;
int n, m;
int fa[N]; //用来存储这个点的父节点 
struct node{
    int from, to, value;
}edge[M << 1]; 
bool cmp(node x, node y){ //定义排序函数 
    return x.value < y.value;
}
int find(int x){ //并查集，找到x的根节点 
    if(fa[x] != x) return fa[x] = find(fa[x]);
    return x;
}
void Kruskal(){ //Kruskal 
    int tot = 0;
    sort(edge + 1, edge + 1 + m, cmp); //将边权进行排序 
    for(int i = 1; i <= m; i++){
        int ft = find(edge[i].to);
        int ff = find(edge[i].from); //分别找到这两个点的根节点 
        if(ft != ff){ //如果不相同证明相连不会有环 
            tot++; //计数器加一 
            fa[ft] = ff; //将这两个点合并 
            ans += edge[i].value; //答案加上这个点的值 
        }
        if(tot == n) break; //如果进行了n次合并，那么退出循环，已经构造出最小生成树了。 
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) fa[i] = i; //最开始这个节点的父节点就是它自己 
    for(int i = 1; i <= m; i++){
        cin >> edge[i].from >> edge[i].to >> edge[i].value; 
    } 
    Kruskal(); //进行Kruskal算法求解 
    cout << ans << endl; //输出答案 
    return 0;
}
//B3604 by szkzyc