题解 | #修复公路#

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

struct DSU {
    int n; vector<int> fa, sz;
    DSU(int n): n(n), fa(n+1), sz(n+1,1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x){ return fa[x]==x? x: fa[x]=find(fa[x]); }
    bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(sz[a]<sz[b]) swap(a,b); fa[b]=a; sz[a]+=sz[b]; return true; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; if(!(cin >> n >> m)) return 0;
    struct E{int u,v; long long t;};
    vector<E> es(m);
    for(int i=0;i<m;i++){ cin >> es[i].u >> es[i].v >> es[i].t; }
    sort(es.begin(), es.end(), [](const E& a, const E& b){ return a.t < b.t; });
    DSU dsu(n);
    int comps = n;
    for(auto &e: es){
        if(dsu.unite(e.u, e.v)){
            if(--comps == 1){ cout << e.t << '\n'; return 0; }
        }
    }
    cout << -1 << '\n';
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in; private final byte[] buf = new byte[1<<16];
        private int p=0,l=0; FastScanner(InputStream is){in=is;}
        private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
        int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
        long nextLong() throws IOException { int c; long s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
    }

    static class DSU {
        int[] fa, sz;
        DSU(int n){ fa=new int[n+1]; sz=new int[n+1]; for(int i=0;i<=n;i++){ fa[i]=i; sz[i]=1; } }
        int find(int x){ return fa[x]==x? x: (fa[x]=find(fa[x])); }
        boolean unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(sz[a]<sz[b]){int t=a;a=b;b=t;} fa[b]=a; sz[a]+=sz[b]; return true; }
    }

    static class E { int u,v; long t; }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        E[] es = new E[m];
        for(int i=0;i<m;i++){ E e=new E(); e.u=fs.nextInt(); e.v=fs.nextInt(); e.t=fs.nextLong(); es[i]=e; }
        Arrays.sort(es, (a,b)-> Long.compare(a.t, b.t));
        DSU dsu = new DSU(n);
        int comps = n;
        for(E e: es){
            if(dsu.unite(e.u, e.v)){
                if(--comps == 1){ System.out.println(e.t); return; }
            }
        }
        System.out.println(-1);
    }
}

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); m = int(next(it))
edges = []
for _ in range(m):
    u = int(next(it)); v = int(next(it)); t = int(next(it))
    edges.append((t, u, v))
edges.sort()

fa = list(range(n+1))
sz = [1]*(n+1)
def find(x: int) -> int:
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x

comps = n
for t,u,v in edges:
    ru, rv = find(u), find(v)
    if ru != rv:
        if sz[ru] < sz[rv]:
            ru, rv = rv, ru
        fa[rv] = ru
        sz[ru] += sz[rv]
        comps -= 1
        if comps == 1:
            print(t)
            break
else:
    print(-1)