题解 P5631 【最小mex生成树】

djh123 · 2019-11-09 07:45:04 · 题解

因为\text{mex}是不在生成树内的最小的自然数，那我们可以考虑枚举答案是x，\text{check}的时候，如果一条边的边权是x，那么这条边就不应该出现在生成树里，否则一定非法。

那么就有一个比较显然的做法：枚举答案x，把边权为x的所有边删掉，看剩下的边能不能求出一棵生成树。

这样直接暴力去做的复杂度是O(mw\log m)的，对于这种删掉一部分边的问题，我们可以考虑用分治去优化这个过程，那么我们就用solve(l,r)就表示权值范围在[l,r]的边没有加进去，每次添加[l,mid]到[mid+1, r]，添加[mid+1, r]到[l, mid]，用可撤销并查集维护连通性即可，复杂度O(m\log m \log w)，实现的稍微好一点就能通过了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6 + 50, M = 4e6 + 50;
int head[N], to[M], nxt[M], val[M], tot;
bool vis[N];

int fa[N], siz[N], cnt, n, m, ans = 0x3f3f3f3f;
struct node {
    int u, v, w;
}e[M];
bool operator < (const node &a, const node &b) {
    return a.w < b.w;
}

int find(int x) { return x == fa[x] ? x : find(fa[x]); }

int unit(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx == fy) return 0;
    if(siz[fx] > siz[fy]) { fa[fy] = fx; siz[fx] += siz[fy]; return fy; }
    else { fa[fx] = fy; siz[fy] += siz[fx]; return fx; }
}

void del(int x) {
    siz[fa[x]] -= siz[x];
    fa[x] = x;
}

void solve(int l, int r, int pos) {
    if(l == r) { if(siz[find(1)] == n) { cout << l; exit(0);} return ; }
    int mid = (l + r) >> 1;
    int tmp = pos, lsbl = 0;
    vector <int> v;
    for(; e[pos].w <= r && pos <= m; ++ pos) if((e[pos].w > mid) && (lsbl = unit(e[pos].u, e[pos].v))) v.push_back(lsbl);
    solve(l, mid, tmp);
    for(int i = v.size() - 1; i >= 0; -- i) del(v[i]); v.clear();
    pos = tmp, lsbl = 0;
    for(; e[pos].w <= mid && pos <= m; ++ pos) if(lsbl = unit(e[pos].u, e[pos].v)) v.push_back(lsbl);
    solve(mid + 1, r, pos);
    for(int i = v.size() - 1; i >= 0; -- i) del(v[i]); v.clear();
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) fa[i] = i, siz[i] = 1;
    for(int i = 1; i <= m; ++ i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    sort(e + 1, e + 1 + m);
    solve(0, e[m].w + 1, 1);
    return 0;
}