题解 - 帖子 - CQUPT OJ

题意为考虑选取某个值以下的所有边使得1到n联通，使用并查集维护连通块信息，先将边按边权排序，直到1和n连通为止，模拟并查集合并的过程即可。也可使用迪杰斯特拉，二分答案加bfs等等做法，均可以通过此题。

#include <bits/stdc++.h>
using namespace std;

int p[400050];
int n,m;

struct edge
{
    int u,v,w;
    /* data */
}e[500050];

bool cmp(edge l,edge r){
    return l.w<r.w;
}

int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}

void merge(int l,int r){
    int fl=find(l),fr=find(r);
    if(fl==fr)return ;
    p[fl]=p[fr];
    return ;
}

int main(){
    // freopen("8.in","r",stdin);
    // freopen("8.out","w",stdout);
    cin>>n>>m;
    for(int x=1;x<=m;x++){
        cin>>e[x].u>>e[x].v>>e[x].w;
    }
    sort(e+1,e+m+1,cmp);
    for(int x=1;x<=n;x++){
        p[x]=x;
    }
    int ans=0;
    while(find(1)!=find(n)){
        ans++;
        merge(e[ans].u,e[ans].v);
    }
    cout<<e[ans].w<<"\n";
    return 0;
}