P5631 最小mex生成树

题目背景

这是一道经典题。

题目描述

给定 \(n\) 个点 \(m\) 条边的无向连通图，边有边权。

设一个自然数集合 \(S\) 的 \(\text{mex}\) 为：最小的、没有出现在 \(S\) 中的自然数。

现在你要求出一个这个图的生成树，使得其边权集合的 \(\text{mex}\) 尽可能小。

【数据范围】

• 对于 \(100\%\) 的数据，\(1\le n \le 10^6\)，\(1\le m \le 2\times 10^6,0\le w \le 10^5\)。

Solution：

非常人类智慧的经典题，首先我们来考虑如何判断答案是否合法，假设我们现在钦定了一个答案ans,那么我们就应该把所有边权不为ans的边全部加入这个图中跑一遍生成树

但是我们发现如果一个个去枚举答案的话那么时间复杂度将变为\(O(n*w*logn)\)这显然是我们所不能接受的，但是答案貌似又不满足单调性

我们考虑如何优化“枚举答案”这一十分不优秀的过程：我们可以思考这个算法暴力在哪：每一次换一个答案就要重新跑一边生成树，这显然是十分不优秀的，我们考虑优化这一过程：

我们考虑进行分治:solve(l,r)表示将所有边权在\([0,l-1]\)U\([r+1,inf]\)的边全部加入了图中。对于结束状态:l==r，如果当前的图是一棵树，那么答案成立，直接输出并结束程序，否则普通return ;

然后我们对于一个区间[l,r]:先将所有满足\(w \in [mid+1,r]\)的边加入图中，然后先递归左子树(为了最小化答案)。
如果程序没结束，我们先删除 \(w \in [mid+1,r]\)的所有边。我们再将\(w \in [l,mid]\)的边加入图中，递归右子树

但是有一点要特别注意的：我们在加边的时候显然不能直接便利整个边集，不然我们的时间复杂度还是会退化到\(O(n*w*logn)\)

注意到：我们在处理solve(l,r)这一函数时，已经完成了所有满足 \(w \in [0,l-1] or [r+1,inf],\)的边的添加.
所以我们多记一个参数：pos，表示第一个满足\(l \le w\)的位置。这样就可以保证我们遍历所有边的复杂度均摊完是\(O(nlogn)\)的

然后再补充一下删除操作：由于我们要做删除，所以在写并查集时不能路径压缩(_显然),然后对于每个删除就将
siz[fa]-=siz[x],fa[x]=x就好了，同时要注意的是，我们每次只能删除在本区间[l,r]内添加的边，所以在储存时切不可混用容器

然后这题就愉快的做完了

Code：

#include<bits/stdc++.h>
const int N=2e6+5;
using namespace std;
struct Edge{
    int u,v,w;
    bool operator <(const Edge &e)const{
        return w<e.w;
    }
}q[N];
int n,m;
int fa[N],siz[N];
int find(int x){return fa[x]==x ? fa[x] : find(fa[x]);}
int merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy)return 0;
    if(siz[fx]<siz[fy])swap(fx,fy);
    fa[fy]=fx,siz[fx]+=siz[fy];return fy;
}
void split(int x)
{
    siz[fa[x]]-=siz[x];
    fa[x]=x;
}
void ANS(int x)
{
    printf("%d\n",x);
    exit(0);
}
void solve(int l,int r,int pos)
{
    if(l==r)
    {
        if(siz[find(1)]==n)ANS(l);
        return ;
    }
    vector<int> E;
    int mid=l+r>>1,x=0;
    for(int i=pos;i<=m&&q[i].w<=r;i++)
    {
        if((q[i].w>mid)&&(x=merge(q[i].u,q[i].v)))
        E.push_back(x);
    }
    solve(l,mid,pos);
    for(int i=E.size()-1;~i;i--){split(E[i]);}E.clear();
    for(int &i=pos;i<=m&&q[i].w<=mid;i++)
    {
        if(x=merge(q[i].u,q[i].v))
        E.push_back(x);
    }
    solve(mid+1,r,pos);
    for(int i=E.size()-1;~i;i--){split(E[i]);}E.clear();
}
void work()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){fa[i]=i,siz[i]=1;}
    for(int i=1,u,v,w;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        q[i]=(Edge){u,v,w};
    }
    sort(q+1,q+1+m);
    solve(0,q[m].w+1,1);
}
int main()
{
    //freopen("P5631.in","r",stdin);
    //freopen("P5631.out","w",stdout);
    work();
    return 0;
}