问题描述

给定一个无向图，要求计算其最小生成树。如果该图不连通，则输出 "orz"。

输入格式

第一行包含两个整数 N 和 M，表示图中有 N 个节点和 M 条无向边。接下来的 M 行每行包含三个整数 X, Y, Z，表示有一条长度为 Z 的无向边连接节点 X 和 Y。

输出格式

如果图是连通的，输出一个整数表示最小生成树的所有边的总长度。如果图不连通，则输出 "orz"。

样例输入

6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2

样例输出

19

数据规模

• 对于 20% 的数据，N≤5，M≤20。
• 对于 40% 的数据，N≤50，M≤2500。
• 对于 70% 的数据，N≤500，M≤10^4。
• 对于 100% 的数据，1≤N≤5000，1≤M≤2×10^5。

最小生成树的定义

最小生成树是指在一个连通无向图中，用最少的边使所有节点连通，并且这些边的总权重最小。一个有 n 个节点的连通无向图至少需要 n-1 条边来保持连通，且不包含环。

Kruskal 算法（贪心）

适用于稀疏图（M 远大于 N）。Kruskal 算法的基本思想是首先对所有的边按权重从小到大排序，然后依次选择最短的边加入生成树，直到选择了 n-1 条边为止。在选择过程中，需要避免形成环，可以使用并查集来高效地判断两个节点是否已经连通。

算法实现步骤

1. 对所有边按权重进行排序。
2. 初始化并查集，每个节点的父节点指向自己。
3. 遍历排序后的边，如果两个节点尚未连通，则将这条边加入生成树，并合并这两个节点所在的集合。
4. 当生成树中的边数达到 n-1 时，算法结束。

时间复杂度

对边进行快速排序的时间复杂度为 O(MlogM)，在 m 条边中找出 n-1 条边的时间复杂度为 O(MlogN)，因此 Kruskal 算法的总时间复杂度为 O(MlogM + MlogN)。通常情况下 M 比 N 大很多，所以时间复杂度主要由 O(MlogM) 决定。

代码实现

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

int n, m, fa[1000001], countt, sum;
struct Edge {
    int u, v, w;
} edges[1000001];

bool compare(Edge a, Edge b) {
    return a.w < b.w;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    fa[y] = x;
    return true;
}

void kruskal() {
    for (int i = 1; i <= m; i++) {
        if (unite(edges[i].u, edges[i].v)) {
            countt++;
            sum += edges[i].w;
        }
        if (countt == n - 1) return;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    sort(edges + 1, edges + m + 1, compare);
    for (int i = 1; i <= n; i++) fa[i] = i;
    kruskal();
    if (countt == n - 1) cout << sum;
    else cout << "orz";
    return 0;
}