解题思路:最小生成树模版题

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int f[1000];
struct node
{
	int from;
	int to;
	int w;
};
int find(int x)
{
	if(x!=f[x])
	{
		return f[x]=find(f[x]);
	}
	return x;
}
long long ans=0;
void meare(node a,bool t)
{
	int x=find(a.from);
	int y=find(a.to);
	if(x!=y)
	{
		f[y]=x;
		if(t)ans+=a.w;
		
	}
}
vector<node>v;
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int main()
{
	int n;
	while(cin>>n&&n)
	{
		ans=0;
		for(int i=0;i<=n;i++)
		{
			f[i]=i;
		}
		for(int i=1;i<=(n*(n-1)/2);i++)
		{
			int d;
			node a;
			cin>>a.from>>a.to>>a.w; 
			v.push_back(a);
		}
		sort(v.begin(),v.end(),cmp);
		for(int i=0;i<v.size();i++)
		{
			meare(v[i],1);
		}
		v.clear();
		cout<<ans<<endl;	
	}
	return 0;
}


点赞(0)
 

0.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论