Kruskal

$O(m*logm)$

C++ 代码

/*

可以允许有重边，对于重复的边，这个算法只会访问两点之间的边一次，也就是重复边其中的一条，而
我们将边的权值从小到大排好序，所以最先访问的一定是最小的，故不用去重操作

利用并查集算法寻找是否两点在一个环中，只适用于两点之间有边的情况

大体步骤：
初始化：并查集
1.按照权值对所有边的从下到大排序
2.遍历所有的边，如果这个边的起始与终止节点没有共同的祖宗节点，把这点加入到树种，并把合并这两个并查集中（则说明，这条边加入进最小生成树时，并不会生成环
3.回归：如果加入的边数小于n-1则说明不存在最小生成树（连通不了所有的节点）

*/

#include<iostream>
#include<algorithm>
#define N 100010
using namespace std;
  int n,m;
struct work{
    int a,b,w;
    bool operator<(const work&t)const{
        return w<t.w;
    }
};
work graph[2*N];
int pre[N];
int find(int x){

    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
int cnt;


long long krusal(){
    long long sum=0;
    for(int i=0;i<m;++i){
        int pa=find(graph[i].a);
        int pb=find(graph[i].b);
        if(pa!=pb){
            cnt++;
            pre[pa]=pb;
            sum+=graph[i].w;
        }

    }
    return sum;

}







int main(){

    cin>>n>>m;
    for(int i=1;i<=n;++i){
        pre[i]=i;
    }
 for(int i=0;i<m;++i){
     int a,b,w;
     cin>>a>>b>>w;
     graph[i].a=a;
     graph[i].b=b;
     graph[i].w=w;

 }
 sort(graph,graph+m);

 int sum=krusal();
 if(cnt<n-1)cout<<"impossible"<<endl;
 else cout<<sum<<endl;


    return 0;
}