知识点

最小生成树

表示一个无向连通图中边权和最小的生成树

并查集

可以实现：

• 合并：合并两个元素所属集合（合并对应的树）

• 查询：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

题目

P3366 【模板】最小生成树

题目描述

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

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例 #1

输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

7

说明 / 提示

数据规模：

对于 $20%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

题解

Prim 算法

Prim 算法的思想是从一个顶点开始，不断扩大生成树，每次选择与当前生成树相连的权值最小的边来加入树中。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = INT_MAX;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>>adj(n + 1);
    for (int i = 0;i < m;i++) {
        int u, v, w;// 一条边，令一条边，权值
        cin >> u >> v >> w;
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    vector<int>d(n + 1, INF);
    vector<bool>vis(n + 1, 0);
    d[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;// 优先队列
    pq.push({ 0,1 });
    int res = 0, cnt = 0;// res权值,cnt边数
    while (!pq.empty()) {
        auto dd = pq.top().first;
        auto u = pq.top().second;
        pq.pop();
        if (vis[u])continue;// 若访问过就跳过
        vis[u] = 1;// 标记访问
        res += dd;// 增加权值
        cnt++;// 增加边数
        for (auto ed : adj[u]) {
            int v = ed.first;// 邻居
            int w = ed.second;// 该顶点和此邻居的边权
            if (!vis[v] && w < d[v]);
            d[v] = w;// 更新最短距离
            pq.push({ w,v });// 入队
        }
    }
    if (cnt == n)cout << res;
    else cout << "orz";
    return 0;
}

剩下两种突然不想写了…… 实则因为以前没写过

反正 Prim 算法就够用了，剩下两个还需要并查集