AcWing 1141. 局域网 题解（kruskalkruskal 求最小生成树）

AcWing 1141. 局域网
克鲁斯卡尔求最小生成森林（就是每个联通块求最小生成树），克鲁斯卡尔的算法过程刚好是从小到大依次将边加入集合中，所以这里刚好利用克鲁斯卡尔算法求

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

int p[N];  //并查集祖先数组
int n, m;
int res;  //记录答案
struct Edge{
    
	int a, b, w;
	bool operator<(const Edge &t) const {
    
		return w < t.w;
	}
}edge[N]; 

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

int main()
{
    
	cin>>n>>m;
	for(int i = 1; i <= n; i ++ ) p[i] = i;  //注意初始化并查集 
	for(int i = 0; i < m; i ++ ){
    
		int a, b, c;
		cin>>a>>b>>c;
		edge[i] = {
    a, b, c};
	}
	
	sort(edge, edge + m);
	
	for(int i = 0; i < m; i ++ ){
    
		//a和b相连才会被遍历到，所以这里不用担心将两个不同的连通块连在一起 
		int a = find(p[edge[i].a]), b = find(p[edge[i].b]);
		if(a != b) p[a] = b;  //如果不在一个集合内，就加入到一个集合内 
		else res += edge[i].w;  //如果这两个点在一个联通块内，说明他们已经通过花费更小的边连在一起，目前这个边就可以删除了 
	}
	cout<<res<<endl;
	return 0;
}