自动搬运

查看原文

来自洛谷，原作者为

	Growl、 **

搬运于2025-08-24 21:26:19，当前版本为作者最后更新于2019-08-27 17:14:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

最小生成树算法

根据题目描述，这道题是最小生成树

树：

树是一种植物，木本植物之总名，主要由根、干、枝、叶、花、果组成

一个不存在回路的无向联通图叫做树

生成树：生成树是连通图的极小联通子图。（加边会出现回路，减边变为非连通图）

最小生成树： 生成树的各边权值总和最小的树（最小代价树）

最小生成树一般有两种算法：prim和kruskal。prim一般用于稠密图，kruskal用于稀疏图。

这里介绍一下kruskal。

kruskal算法的基本思想是：始终选择当前可用的最小权值边（贪心

因此很容易想到题目所求的最大边就是最后一条边（每次加边权取max也可以）。

那么怎么判断当前选择的边是否可用呢？

并查集

意思就是说，开始的每个点都是独立的集合，加边的时候就合并起来，如果已经是联通的就跳过。

附上代码```

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int fa[200004];
int n,m,l,r,tot,ans,k;

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}//快读 

struct node{
	int fir;//第一个点 
	int sec;//第二个点 
	int data;//边权 
}edge[400005];

inline int find(int x){
	if(x==fa[x])return x;
	else return fa[x]=find(fa[x]);
}

inline bool cmp(node a,node b){
	return a.data<b.data;//结构体排序 
}

inline void kruskal(){
	for(register int i=1;i<=m;i++){
		l=find(edge[i].fir);
		r=find(edge[i].sec);
		if(l==r)continue ;//如果联通就跳过 
		fa[l]=r;//否则就合并 
		k=edge[i].data;//每次更新边权，最后一条边为最大 
	//	maxn=max(maxn,edge[i].data);每次加边取max也可以 
		tot++;
		if(tot==n-1)break;
	}
}

int main(){
	n=read();
	m=read();
	for(register int i=1;i<=n;i++)
	fa[i]=i;//初始化并查集 
	for(register int i=1;i<=m;i++){
		edge[i].fir=read();
		edge[i].sec=read();
		edge[i].data=read();
	}
	
	sort(edge+1,edge+m+1,cmp);//将边权排序，每次加小的 
	kruskal();
	cout<<k;//我喜欢cout...
	 
	return 0;
}