自动搬运

查看原文

来自洛谷，原作者为

	ggpw_XNW 弱小和无知从来都不是生存的障碍，傲慢才是！

搬运于2025-08-24 23:13:49，当前版本为作者最后更新于2025-04-19 14:18:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

首先根据图的基本知识可以知道 $n-1$ 条边能让城市联通的边，答案就是这些边最长一条的长度，要让这个长度最短。
简言之：求出一棵最长边最短的树。

算法

这就是瓶颈生成树了。无向图 $G$ 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 $G$ 的所有生成树中最小。
我们来看一个性质：最小生成树是瓶颈生成树，但瓶颈生成树不一定是最小生成树。 为什么？最小生成树是让这棵树的边权和最小，而瓶颈生成树是让最长边最短。也就是说最小生成树的最长边就是瓶颈生成树的最长边。因为瓶颈生成树的最长边最短，而最小生成树是所有生成树中最小的（边权），所以最长边一定相同。
所以我们可以写最小生成树。

代码

然后就是模板代码了。

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
	int x , y , len;
}a[200005];
int n , ans , m , f[200005];
bool cmp(node A , node B){
	return A.len < B.len;
}
int find(int x){
	if(f[x]==x)return x;
	return f[x] = find(f[x]);
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++)cin >> a[i].x >> a[i].y >> a[i].len;
	for(int i=1;i<=n;i++)f[i] = i;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(find(a[i].x)!=find(a[i].y))f[find(a[i].x)] = find(a[i].y) , ans = max(ans,a[i].len) , n--;
	}
    if(n>1)ans = -1;
	cout << ans;
	return 0;
}

相信大家都会用并查集吧，如果不会请去 P3367，这里就不多说了。

注意事项：

1. 并查集务必赋初始值！不赋后果自负！
2. 路径压缩！
3. 排序！
4. 判断无解！
5. 不要抄袭！