【洛谷P5631】最小mex生成树 | Mrsrz's blog

线段树分治+可撤销并查集

题目大意：

给定一张无向图连通图，带边权。

求一棵生成树，满足其边权的 mex 最小。

求最小 mex。

mex 为最小的未出现的自然数。

题解：

当 mex 为 $w$ 的时候，边权为 $w$ 的边一定不能出现。

那么边权为 $w$ 的边，只能在 mex 为 $[0,w-1]$ 或 $[w+1,+\infty]$ 时出现。

线段树分治，对于边权为 $w$ 的边，在 $[0,w-1]$ 和 $[w+1,+\infty]$ 处插入这条边。

然后遍历，用并查集维护连通状态。当前线段树区间为 $[l,r]$ 时，满足使用的边中一定没出现过边权在 $[l,r]$ 之间的边。由于我们遍历线段树时，先遍历左边再遍历右边，任意时刻，连通块个数为 $1$ 时，即可得到最小 mex。

时间复杂度 $O(m\log n\log w)$，空间复杂度 $O(m\log w)$。

Code：

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int M=1e6+5,N=1e5+5;
struct edge{
    int u,v,w;
}e[M<<1];
vector<int>vec[N<<2];
char buf[(int)2e8],*ss=buf;
inline int init(){buf[fread(buf,1,(int)2e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
int n,m,mxb,fa[M],sz[M],bl,sta[M<<1],top;
inline int find(int x){while(x!=fa[x])x=fa[x];return x;}
void add(int l,int r,int o,const int&L,const int&R,const int&id){
    if(L<=l&&r<=R)vec[o].push_back(id);else{
        const int mid=l+r>>1;
        if(L<=mid)add(l,mid,o<<1,L,R,id);
        if(mid<R)add(mid+1,r,o<<1|1,L,R,id);
    }
}
void solve(int l,int r,int o){
    const int TOP=top,BL=bl;
    for(int id:vec[o]){
        int x=find(e[id].u),y=find(e[id].v);
        if(x!=y){
            if(sz[x]<sz[y])swap(x,y);
            sz[x]+=sz[y],fa[y]=x;
            sta[++top]=y;
            --bl;
        }
    }
    if(bl==1){
        printf("%d\n",l);
        exit(0);
    }
    const int mid=l+r>>1;
    if(l<r)solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
    while(top!=TOP){
        int y=sta[top--];
        sz[fa[y]]-=sz[y],fa[y]=y;
    }
    bl=BL;
}
int main(){
    n=readint(),m=readint();
    for(int i=1;i<=m;++i){
        e[i].u=readint(),e[i].v=readint();
        mxb=max(mxb,e[i].w=readint());
    }
    for(int i=1;i<=m;++i){
        if(e[i].w)
        add(0,mxb,1,0,e[i].w-1,i);
        if(e[i].w<mxb)
        add(0,mxb,1,e[i].w+1,mxb,i);
    }
    for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    bl=n;
    solve(0,mxb,1);
    printf("%d\n",mxb+1);
    return 0;
}