题意

题目链接

easy version 中要求的是将第一条边最大修改为多少能够使其存在在最小生成树中。

解析

题目与最小生成树相关，又要值尽可能大，很容易想到 kruskal 算法，因为该算法是先将权值小的边加入到最小生成树中的，因此，我们希望第一条边能够尽可能晚的加入到最小生成树中，这样才能使其权值最大。

考虑到要使其尽可能晚加入而且不能不加入，因此我们希望在第一条边的两点联通之前连接尽可能多的边，如果一条边连接后，第一条边的两点被联通了，显然第一条边就无法加入到最小生成树中了，因此我们需要在这个刚好被联通的临界点加入第一条边，即将第一条边的权值修改为临界边的权值（题目要求可能出现，因此可以等于临界边的权值，即直接赋值）。

我们又考虑到，可能存在第一条边为割边，即第一条边如果不加入到最小生成树中，其他边就无法构成最小生成树的情况，也就是在第一条边不遍历的情况下， $cnt$ 无法等于 $n-1$ ，此时将第一条边的值赋为最大,即题面所述的 $10^9$ 即可。

而我们将该思想进行代码实现时，只需要忽略第一条边，让其他边正常跑 kruskal 即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int n,m,fa[N],cnt;
struct edge{
    int u,v,val;
}e[N];
inline int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
inline bool cmp(edge i,edge j){
    return i.val<j.val;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].val);
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    sort(e+2,e+1+m,cmp);//忽略第一条边跑 kruskal 
    for(int i=2;i<=m&&cnt<n-1;i++){
        int u=e[i].u,v=e[i].v;
        if(find(u)==find(v)) continue;
        fa[find(u)]=find(v);
        cnt++;
        if(find(e[1].u)==find(e[1].v)){
            printf("%d\n",e[i].val);
            return 0;
        }   
    }
    if(cnt<n-1){//如果是割边 
        cout<<(int)1e9;
    }
    return 0;
}