题目描述

blablabla

样例

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010,M=200010,INF=0x3f3f3f3f;
int p[N];
int n,m;
struct Edge{
    int a,b,w;
    bool operator <(const Edge &W)const
    {return w<W.w;}
}edge[M];
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int kruskal()
{
    sort(edge,edge+m);
    for(int i=1;i<=n;i++) p[i]=i;
    int cnt=0,res=0;//res树边树边权重之和，cnt集合中的边数
    for(int i=0;i<m;i++)
    {
        int a=edge[i].a,b=edge[i].b,w=edge[i].w;
        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            cnt++;

        }
    }
    if(cnt!=n-1) return 0x3f3f3f3f;//最小生成树n个点，n-1条边，否则都不存在最小生成树
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge[i]={x,y,z};
    }
    if(kruskal()==0x3f3f3f3f)   puts("impossible");
    else cout<<kruskal();
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla