题解 | 【模板】最小生成树 #

$[模板+Prim+Kruskal ]$

给定一个无向连通有权图 $G=(V,E)$ ，其中 $V$ 是顶点集， $E$ 是边集，边权为 $W_{e}$

生成树的概念：是 $G$ 的一个子图，满足：

包含 $G$ 的所有 $n$ 个顶点
有且仅有 $n-1$ 条边
子图是连通的，且无环

最小生成树的概念：在所有的生成树中，边权值和最小的生成树

判断能否构成一棵最小生成树以及求出最小生成树的边权值之和有两种方法：

$Prim$ 算法，时间复杂度为 $mlogn$

$Prim$ 算法基于贪心的思想，每次找已选点集合与未选点集合之间权值最小的边连接

详细解释这一段代码：

$dist[i]$ 表示的是 $i$ 这个还没选进入最小生成树的点与已经选进入最小生成树的点之间构成边的最小边权值

所以如果 $dist[v]>w$ ，说明有最小的一条边可以选择，这样最小生成树的边总权值可以最小！

for(auto [v, w] : adj[u]){
    if(!vis[v] && w < dist[v]){
        dist[v] = w;
        q.push({v, dist[v]});
    }
}

模板代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 3e5 + 10;

int n, m;
vector<pair<int, int> > adj[N];
int dist[N];
bool vis[N];

struct cmp{
    bool operator() (const pair<int, int> a, const pair<int, int>  b){
        return a.second > b.second;
    }
};
int prim(){
    priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> q;
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[1] = 0;
    q.push({1, 0});

    int node_cnt = 0, node_sum = 0;
    while(q.size()){
        pair<int, int> now = q.top();
        q.pop();
        int u = now.first, w = now.second;
        if(vis[u]) continue;
        vis[u] = true;

        node_cnt ++;
        node_sum += w;
        for(auto [v, w] : adj[u]){
            if(!vis[v] && w < dist[v]){
                dist[v] = w;
                q.push({v, dist[v]});
            }
        }
    }
    if(node_cnt == n) return node_sum;
    else return -1;
}
signed main(){
    HelloWorld;
    
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    int res = prim();
    if(res == -1) cout << "NO" << endl;
    else cout << res << endl;
    return 0;
}

$Kruskal$ 算法，时间复杂度为 $mlogm$

同样基于贪心的思想，首先将所有边按照权值从小到大排序，然后依次添加进入最小生成树里面；因为是按照边权值从小到大排序，所以这样遍历最后得到的生成树的边总权值一定最小。

当然如果两个点已经连通了，那么就不用再添加了，所以用并查集维护一下

模板代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 3e5 + 10;

int n, m, p[N];
struct Node{
    int u, v, w;
};

bool cmp(Node a, Node b){
    return a.w < b.w;
}

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

signed main(){
    HelloWorld;
    
    cin >> n >> m;
  
    vector<Node> node(m + 1);
    for(int i = 1; i <= m; i ++){
        int u, v, w; cin >> u >> v >> w;
        node[i] = {u, v, w};
    }
    sort(node.begin() + 1, node.begin() + 1 + m, cmp);
    for(int i = 1; i <= n; i ++) p[i] = i;
    int ans_cnt = 0, ans_sum = 0;

    for(int i = 1; i <= m; i ++){
        if(ans_cnt == n - 1) break;
        int u = node[i].u, v = node[i].v, w = node[i].w;
        int fu = find(u), fv = find(v);
        if(fu != fv){
            p[fu] = fv;
            ans_cnt ++;
            ans_sum += w;
        }
    }
    if(ans_cnt != n - 1) cout << "NO" << endl;
    else cout << ans_sum << endl;
    return 0;
}