克鲁斯卡尔

$O(nlogn)$

C++ 代码

// 先排序在一条边一条边的加 并查集也可以用
// 不得不说vector是真的慢
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5+10;
vector<vector<int>> edge; // 用来存边
int p[N / 2];
int n, m, sum;

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

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

    cin >> n >> m;

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

    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({c, a, b});
    }

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

    int num = 1;
    for(int i = 0; i < edge.size(); i ++)
    {
        int a = edge[i][1], b = edge[i][2], c = edge[i][0];
        if(find(a) == find(b)) continue;
        sum += c;
        num ++;
        p[find(a)] = find(b);
    }
    if(num == n) cout << sum;
    else cout << "impossible";
    return 0;
}