嗯...

 

题目链接：

 

思路：

嗯...既然题中已经说了是最小生成树，那么是需要在最小生成树的模板上稍作修改即可。要求的是最小生成树中的最长边，注意：

一. 不是每一条边都可以做为最小生成树中的边。

二. 所要求的这条边是连接两个点的边的最大权值。

所以，我们就在“并”操作的时候稍作修改，用ans记录下它的最大权值即可。

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int f[100005]; 8 int ans; 9 10 struct node{11     int x, y, l;12 } a[1000005];13 14 inline int cmp(node i, node j){15     return i.l < j.l;16 }17 18 inline int find(int x){19     if(f[x] != x)20         f[x] = find(f[x]);21     return f[x];22 }//"查" 23 24 int main(){25     int n, m;26     scanf("%d%d", &n, &m);27     for(int i = 1; i <= m; i++){28         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l);29     }30     for(int i = 1; i <= n; i++)31         f[i] = i;32     sort(a+1, a+1+m, cmp);//按边权排序，"最小" 33     for(int i = 1; i <= m; i++){34         int r1 = find(a[i].x);35         int r2 = find(a[i].y);36         if(r1 != r2){37             f[r1] = r2;38             ans = max(ans, a[i].l);//维护最大边权 39         }//"并" 40     }41     printf("%d", ans);42     return 0;43 }