给定结点数为 n，边数为 m 的带权无向连通图 G，所有结点编号为 1,2,…n。 求 G 的最小生成树的边权和 输入格式 第一行两个正整数 n，m。 之后的 m 行，每行三个正整数 u，v，w（1≤u，v≤n，0≤w≤10^9），描述一条连接结点 u 和 v，边权为 w 的边。 输出格式 一个整数表示 G 的最小生成树的边权和。 样例数据 输入 7 12 1 2 9 1 5 2 1 6 3 2 3 5 2 6 7 3 4 6 3 7 3 4 5 6 4 7 2 5 6 3 5 7 6 6 7 1 输出 16

这道题是经典的最小生成树问题，可以使用 Kruskal 或者 Prim 算法进行求解。以下是 Kruskal 算法的实现。

Kruskal 算法流程：

1. 将所有边按照权重从小到大排序
2. 依次考虑每条边，如果加入这条边不会形成环，则将其加入最小生成树中
3. 最终得到的就是最小生成树

Kruskal 算法的实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int p[N];   // 并查集数组

struct Edge
{
    int a, b, w;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}edges[M];

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

int kruskal()
{
    for (int i = 1; i <= n; i++) p[i] = i;

    sort(edges, edges + m);

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            p[pa] = pb;
            res += w;
            cnt++;
            if (cnt == n - 1) break;   // 已经选了 n-1 条边，构成了最小生成树
        }
    }

    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int res = kruskal();
    cout << res << endl;

    return 0;
}