题解：P12222 [蓝桥杯 2023 国 Java B] 电动车

· · 题解

分析

首先根据图的基本知识可以知道 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. 不要抄袭！