F - Agri-Net （最小生成树&kruskal）

F - Agri-Net （最小生成树&kruskal）

思路：板子题。（第一次学这个算法标记一下）。思路就是对边排序，取n-1条边生成一棵权值和最小的树。生成树的过程用并查集实现。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue> 
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e2+5;
int n,s[N];
struct edge{
	int u,v,w;
	bool operator<(const edge&a)const{ //重载'＜' 
		return w<a.w;
	}
}now;
vector<edge>e;
int find(int x){
	if(s[x]!=x) s[x]=find(s[x]);
	return s[x]; 
}
int kruskal(){
	int ans=0;
	for(int i=1;i<=n;i++) s[i]=i;
	sort(e.begin(),e.end());//排序 
	int tot=0;
	for(int i=0;i<e.size();i++){
		int fa=find(e[i].u),fb=find(e[i].v);
		if(fa==fb) continue;//防止生成环. 
		tot++;
		s[fb]=fa;
		ans+=e[i].w;
		if(tot==n-1) break; //n-1条边生成一棵树. 
	}
	return ans;
}
int  main(){
	while(~scanf("%d",&n)){
		e.clear();//初始化 
	for(int i=1;i<=n;i++)
		for(int j=1,w;j<=n;j++)
		{
			scanf("%d",&w);
			if(i>j) e.push_back({i,j,w});//防止重边 
		}
		printf("%d\n",kruskal());
	}
		return 0;
}