C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

vector<pair<int, PII>> vec;//用pair<int, pair<int, int>>类型将a b c存储进动态数组中，之后用sort排序可不需要重载小于号
int n, m;
int p[N];
int res, cnt;

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

    p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;

        vec.push_back({c, {a, b}});
    }

    sort(vec.begin(), vec.end());

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

    for(int i = 0; i < vec.size(); i ++)
    {
        int c = vec[i].first, a = vec[i].second.first, b = vec[i].second.second;

        int ra = find(a), rb = find(b);

        if(ra == rb)
            continue;

        else
        {
            p[ra] = rb;
            res += c;
            cnt ++;
        }
    }

    if(cnt == n - 1)
        cout << res << endl;

    else
        cout << "impossible" << endl;
}