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;
} 
全部评论

相关推荐

好想摆:一想到我苦苦追求的迪子私下里却是985的马子,我的心就在滴血😭😭😭
点赞 评论 收藏
分享
昨天 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务