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

heyou666 · 2025-05-04 14:43:52 · 题解

思路：瞄一眼题目，是要求连通图中最大边权最小值，想到瓶颈生成树，再看到无向图（这里有个特殊性质，无向图中的瓶颈生成树一定是最小生成树），很容易联想到 Kruskal 算法中的最小生成树最大边。所以我们只需要按边排序后检查边是否联通，不联通连接即可，由于边排序过，所以最后一条连接的边即为树中边权最大的。

Code:

#include<bits/stdc++.h>
using namespace std;
struct dsu {
    vector<int>pa,size;
    int count;
    dsu(int n) {
        count = n;
        pa = size = vector<int>(n + 1, 1);
        iota(pa.begin(),pa.end(),0);
    }
    int find(int x) {
        return pa[x] == x ? x : pa[x] = find(pa[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (size[x] < size[y]) swap(x, y);
        pa[y] = x;
        size[x] += size[y];
        count--;
    }
    bool pd(int x,int y) {
        return find(x) == find(y);
    }
};
struct edge{
    int u,v,w;
    bool operator < (const struct edge & rhs){
        return w<rhs.w;
    }
}e[200010];//按边排序
long long n,m,u,v,s,t,mi=INT_MAX;
vector<long long> g[200010];
long long node[200010],vis[200010];
int main(){
    cin>>n>>m;
    struct dsu uf(n);
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        if(uf.pd(e[i].u,e[i].v)){
            continue;//已经连通就放弃
        }else{
            uf.merge(e[i].u,e[i].v);
        }
        if(uf.count==1){
            cout<<e[i].w<<endl;//图已经联通，这是最后且最大的一条边
            return 0;
        }
    }
    cout<<"-1"<<endl;//没结束说明不联通
    return 0;
}