题目描述

解释后面来补

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2*N, INF = 0x3f3f3f3f;
int p[N];
int n,m;
struct Edge
{
    int a,b,c;
    bool operator < (Edge&w) const
    {
        return w.c > c;
    }
}edge[M];
int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    int res = 0;
    int cnt = 0; 
    for(int i = 0; i <= n ; i++ ) p[i] = i;
    sort(edge,edge+m);
    for(int i = 0; i < m; i ++ )
    {
        int a = edge[i].a,b = edge[i].b,c = edge[i].c;
        a = find(a),b = find(b);
        if(a!=b)
        {
            p[a] = b;
            cnt++;
            res += c;
        }
    }
    if(cnt < n- 1) return INF;
    return res ;
}

int main ()
{
    cin >> n >> m;
    for(int i = 0; i < m ; i ++ )
    {
        int a,b,c;
        cin >> a >> b >> c;
        edge[i] = {a,b,c};
    }
    int t = kruskal();
    if(t>=INF / 2)  cout << "impossible" << endl;
    else   cout << t << endl;

    return 0;
}