算是 Boruvka 一次正经的应用..

Problem

与运算最大生成树

Solution

维护 Trie。
考虑如果该位为 0 的话得往 1 和 0 子树都遍历一遍，这样不好。
所以把 1 子树的信息直接 复制 到 0 子树（注意不能直接引用子树的指针，会出问题）。

那么这就是一个完全二叉树，最多有 $2^{m+1}$ 个点。

然后每个节点维护节点所属集合编号的 min,max，仅仅只是为了查询能不能合并和保存两种集合的信息而已，min，max 本身没什么实际含义，但很巧妙。

Boruvka 要求在一次扩展的途中复杂度做到 $O(n+m)$ 同阶，那么这个算法复杂度就是合法的。因此你可以省去许多不必要的细节而避免被困入其中。

Code

// Code by ajcxsu
// Problem: newyear's trie

#include<bits/stdc++.h>
using namespace std;

const int N=(2<<20)+10, M=1e5+10;
struct Node *nil;
struct Node {
    Node *ch[2];
    int mi, mx;
    Node() { ch[0]=ch[1]=nil; mi=0x3f3f3f3f, mx=-0x3f3f3f3f; }
    void upd() { mi=min(ch[0]->mi, ch[1]->mi), mx=max(ch[0]->mx, ch[1]->mx); }
} *rt, po[N], *pp=po;
void ini() { pp=po, nil=pp++, nil->ch[0]=nil->ch[1]=nil, rt=pp++, *rt=Node(); }

int fa[M], val[M], to[M], tow[M], rk[M];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
int Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return 0;
    if(rk[af]>rk[bf]) swap(af, bf);
    fa[af]=bf, rk[bf]=max(rk[bf], rk[af]+1);
    return 1;
}
typedef long long ll;
ll ans;
int n, m;

void ins(int &x, int id) {
    Node *nd=rt;
    for(int i=m;i>=0;i--) {
        nd->mi=min(nd->mi, id), nd->mx=max(nd->mx, id);
        if(nd->ch[bool(x&(1<<i))]==nil) nd->ch[bool(x&(1<<i))]=pp++, *nd->ch[bool(x&(1<<i))]=Node();
        nd=nd->ch[bool(x&(1<<i))];
    }
    nd->mi=min(nd->mi, id), nd->mx=max(nd->mx, id);
}

void merge(Node *&x, Node *y) {
    if(y==nil) return;
    if(x==nil) x=pp++, *x=Node();
    merge(x->ch[0], y->ch[0]);
    merge(x->ch[1], y->ch[1]);
    x->mi=min(x->mi, y->mi), x->mx=max(x->mx, y->mx);
}
void dfs(Node *x) {
    if(x==nil) return;
    dfs(x->ch[1]), dfs(x->ch[0]), merge(x->ch[0], x->ch[1]);
}
pair<int, int> query(Node *x, int val, int t, int ty, int ans) {
    if(t==-1) return make_pair(ans, x->mi==ty?x->mx:x->mi);
    if((val&(1<<t)) && x->ch[1]!=nil && (x->ch[1]->mi!=x->ch[1]->mx || x->ch[1]->mi!=ty)) return query(x->ch[1], val, t-1, ty, ans|(1<<t));
    else return query(x->ch[0], val, t-1, ty, ans);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>m, m--;
    for(int i=1;i<=n;i++) cin>>val[i];
    int cnt=0;
    while(cnt!=n-1) {
        ini();
        for(int i=1;i<=n;i++) ins(val[i], Find(i));
        dfs(rt);
        memset(tow, 0, sizeof(tow));
        if(rt->mi==rt->mx) break;
        int fai;
        for(int i=1;i<=n;i++) {
            fai=Find(i);
            auto na=query(rt, val[i], m, fai, 0);
            if(na.first>tow[fai]) to[fai]=na.second, tow[fai]=na.first;
        }
        for(int i=1;i<=n;i++) if(!fa[i] && Union(to[i], i)) ans+=tow[i], cnt++;
    }
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uoj-176.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆