[C++] P3366 【模板】最小生成树

发表于 分类于

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1
7

说明/提示

数据规模：

对于 20% 的数据，N ≤ 5，M ≤ 20。

对于 40% 的数据，N ≤ 50，M ≤ 2500。

对于 70% 的数据，N ≤ 500，M ≤ 104。

对于 100% 的数据：1 ≤ N ≤ 5000，1 ≤ M ≤ 2 × 105，1 ≤ Zi ≤ 104。

样例解释：

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

题解

并查集+优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
    int src, dest, weight;
    bool operator<(const Edge& other) const {
        return weight > other.weight;
    }
};

int find(vector<int>& parent, int i) {
    if (parent[i] == i) return i;
    parent[i] = find(parent, parent[i]);
    return parent[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    priority_queue<Edge> edges;

    for(int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edges.push({a, b, c});
    }

    vector<int> parent(n);
    for (int i = 0; i < n; ++i) parent[i] = i;

    int edgeCount = 0, total = 0;
    while (!edges.empty()) {
        Edge nextEdge = edges.top();
        // cout << "Get an edge with src=" << nextEdge.src << ", dst=" << nextEdge.dest << ", wgt=" << nextEdge.weight << endl;
        edges.pop();
        int x = find(parent, nextEdge.src);
        int y = find(parent, nextEdge.dest);
        // cout << nextEdge.src << " is pointing to " << x << endl;
        // cout << nextEdge.dest << " is pointing to " << y << endl;

        if (x != y) {
            // cout << "Now " << x << " is pointing to " << y << endl;
            parent[x] = y;
            total += nextEdge.weight;
            edgeCount++;
        }
    }

    if(edgeCount == n - 1) cout << total << endl;
    else cout << "orz" ;//<< edgeCount << endl;

    return 0;
}