【LOJ#123】最小生成树，Kruskal模板

probelm

• 给出n个点m条边的图，求最小生成树的边权和

solution

• 将所有边按照边权从小到大顺序排序。
• 如果一条边加入之后不存在环就加入。
• 用并查集维护点的连通性。
• 时间复杂度O(mlogm)

//code2 2021.03.07
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
const int mod = 1000;

struct Edge{
    int u, v, w;
    Edge(int u=0, int v=0, int w=0):u(u),v(v),w(w){}
    bool operator < (Edge b)const{return w<b.w;}
};

int fa[maxn];
void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

int main(){
	int n, m;  cin>>n>>m;
	vector<Edge>e;
	for(int i = 0; i < m; i++){
		int u, v, w;  cin>>u>>v>>w;
		e.push_back({u,v,w});
	}
	sort(e.begin(),e.end());
	LL ans = 0;  init(n);
	for(int i = 0; i < m; i++){
		int u = e[i].u, v = e[i].v;
		if(find(u) != find(v)){
			merge(u,v);
			ans += e[i].w;
		}
	}
	cout<<ans<<"\n";
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

//codes1 2017.05.18
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 500010;

int n, m;
struct Edge{ int u, v, w; }e[maxn];
bool cmp(Edge a, Edge b){return a.w<b.w;}

int fa[maxn];
void init(int _n){
	for(int i = 1; i <= _n; i++)fa[i] = i;
}
int find(int x){
	return fa[x]==x? x : fa[x] = find(fa[x]);
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i = 1; i <= m; i++)
		cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1,cmp);
	long long ans = 0;
	init(n);
	for(int i = 1; i <= m; i++){
		if(find(e[i].u) != find(e[i].v)){
			fa[find(e[i].u)] = find(e[i].v);
			ans += e[i].w;
		}
	}
	cout<<ans<<'\n';
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/114498774