自动搬运

查看原文

来自洛谷，原作者为

	Leonid 我要逃离这里

搬运于2025-08-24 21:13:49，当前版本为作者最后更新于2021-07-29 11:15:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3604 [图论与代数结构 302] 最短树问题_2

这道题是一道裸的求最小生成树，难度普及—。

算法：Kruskal

Kruskal 是一种贪心求最小生成树的算法，非常de好用。

值得注意的是：$1 \le n \le 100000,1 \le m \le 300000$ ,边权均是 $[0,10^9]$ 中的整数。所以我们需要用到 long long 类型存储答案。

那么这道题就很轻松的通过啦。

My Code：

#include<cstdio>
#include<algorithm> //sort头文件

using namespace std;

#define int long long //注意long long，我在这里被卡了2次

int n,m,fa[300005],ans;
struct node{
	int x,y,z;
}h[300005]; //结构体存图

bool operator < (node x,node y){
	return x.z<y.z;
} //重载运算符，跟手写一个cmp没什么区别

int get(int x){
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
} //并查集

void Kruskal(){
	sort(h+1,h+m+1);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x=get(h[i].x),y=get(h[i].y);
		if(x==y)continue;
		fa[x]=y;
		ans+=h[i].z;
	}
} //贪心法求最小生成树

signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%lld %lld %lld",&h[i].x,&h[i].y,&h[i].z); //存图
	Kruskal();
	printf("%lld",ans);
	return 0; //完美结束qwq
}

蒟蒻的第一篇题解，望管理员大大通过。