题意：读清楚之后发现就是求最小瓶颈路的瓶颈，而容易知道求最小瓶颈路就是求最小生成树的最大边
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #define LL long long 6 #define debug(x) cout << "[" << x << "]" << endl 7 using namespace std; 8 9 const int mx = 1e5+10; 10 11 struct edge{ 12 int u, v, w; 13 edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){} 14 bool operator < (const edge& a) const { 15 return w < a.w; 16 } 17 }e[mx*2]; 18 int pa[mx]; 19 20 int fx(int x){ 21 return pa[x] == x ? x : pa[x] = fx(pa[x]); 22 } 23 24 int main(){ 25 int n, m, u, v, w; 26 scanf("%d%d", &n, &m); 27 for (int i = 0; i < m; i++){ 28 scanf("%d%d%d", &u, &v, &w); 29 e[i] = edge(u, v, w); 30 } 31 for (int i = 1; i <= n; i++) pa[i] = i; 32 sort(e, e+m); 33 int ans = 0; 34 for (int i = 0; i < m; i++){ 35 int a = fx(e[i].u), b = fx(e[i].v); 36 if (a != b){ 37 pa[a] = b; 38 ans = max(ans, e[i].w); 39 } 40 if (fx(1) == fx(n)) break; 41 } 42 printf("%d\n", ans); 43 return 0; 44 }