Luogu

分析

枚举一个答案 $ans$，那么我们相当于要求在删去边权为 $ans$ 的边后图是否存在一棵生成树，即图是否连通。

显然可以考虑线段树分治。
具体的，建一棵以边权为下标的线段树，对于每条边权为 $w$ 的边将其放到 $[0,w-1]$ 和 $[w+1,10^5]$ 上。
然后在线段树上遍历，遍历到一个节点就将它上面挂着的边连上，这样子到叶结点时就连上了所有不包含该边权的边，判断图是否连通即可。

用一个可撤销并查集维护上述过程即可。

时间复杂度两个 $\log$，但是它过了 /jk

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10,M=2000000+10,L=100000;

int n,m;

int fa[N],sz[N],sta[N],top=0;
inline int find(int x) { return x==fa[x]?x:find(fa[x]); }
inline void merge(int x,int y) {
    x=find(x),y=find(y);
    if (x==y) return;
    if (sz[x]>sz[y]) swap(x,y);
    fa[x]=y,sz[y]+=sz[x],sta[++top]=x;
}
inline void undo(int pos) {
    while (top>pos) { int x=sta[top--]; sz[fa[x]]-=sz[x],fa[x]=x; }
}

#define ls (o<<1)
#define rs (o<<1|1)
vector<pair<int,int> > vec[L<<2];
inline void modify(int o,int l,int r,int ql,int qr,pair<int,int> e) {
    if (ql<=l&&r<=qr) { vec[o].push_back(e); return; }
    int mid=(l+r)>>1;
    if (ql<=mid) modify(ls,l,mid,ql,qr,e);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,e);
}
inline void solve(int o,int l,int r) {
    int tmp=top;
    for (re auto i:vec[o]) merge(i.first,i.second);
    if (l==r) {
        if (sz[find(1)]==n) { printf("%d\n",l); exit(0); }
    } else {
        int mid=(l+r)>>1;
        solve(ls,l,mid),solve(rs,mid+1,r);
    }
    undo(tmp);
}
#undef ls
#undef rs

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        if (w>0) modify(1,0,L,0,w-1,make_pair(u,v));
        if (w<L) modify(1,0,L,w+1,L,make_pair(u,v));
    }
    for (re int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
    solve(1,0,L);
    return 0;
}