déce. 23 Out of Hay S

https://www.luogu.com.cn/problem/P1547

最小生成树中的最长边是最后被加入的

#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef long long ll;

int in{
    int i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=1e4+5;
int n,m,fa[N],cnt;
struct edge{
    int u,v,w;
    edge(){};
    edge(int U,int V,int W){u=U, v=V, w=W;}
    friend  bool operator < (const edge &a, const edge &b){return a.w<b.w;}
}e[N];

int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}

int main(){

    // freopen("1.in","r",stdin);

    n=in,m=in;
    for(int i=1;i<=m;++i){
        int u=in,v=in,w=in;
        e[i]=edge(u,v,w);
    }

    sort(e+1,e+m+1);
    for(int i=1;i<=n;++i) fa[i]=i;

    for(int i=1;i<=m;++i){
        int u=get(e[i].u),v=get(e[i].v);
        if(u==v) continue;
        ++cnt;
        fa[u]=v;
        if(cnt==n-1){
            printf("%d\n",e[i].w);
            return 0;
        }
    }
    
}