CF888G Xor-MST [Trie/Boruvka/启发式合并]

Author Avatar
空気浮遊 2018年10月03日
  • 在其它设备中阅读本文章
  • 启发式合并
  • 生成树
  • Boruvka
  • 贪心
  • Trie
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

VSC 写的第一道题,纪念。

Problem

最小异或生成树。

Solution

填坑。

考虑 Boruvka,Trie 树上越近的两个点合并越好。

因此模拟从下往上合并,过程中暴力查找 Trie 树上的两个较小子树,贪心即可。

因为觉得代码很难写所以坑了很久,这次写代码过程竟然很平稳

Code

// Code by ajcxsu
// Problem: xor-mst

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

const int N=6e6;
struct Node {
    Node * ch[2];
    char end; int siz;
} *rt, po[N], *pp=po;
void ini() {
    rt=pp++;
}

void ins(int x) {
    Node *nat=rt;
    for(int i=30;i>=0;i--) {
        if(!nat->ch[bool(x&(1<<i))]) nat->ch[bool(x&(1<<i))]=pp++;
        nat=nat->ch[bool(x&(1<<i))];
    }
    nat->end=1;
}

typedef long long ll;
ll ans=0;
int nmin;
void dfs2(Node *x, Node *y, int val, int t) {
    if(t==-1) nmin=min(nmin, val);
    if(x->ch[0]) {
        if(y->ch[0]) dfs2(x->ch[0], y->ch[0], val, t-1);
        else if(y->ch[1]) dfs2(x->ch[0], y->ch[1], val|(1<<t), t-1);
    }
    if(x->ch[1]) {
        if(y->ch[1]) dfs2(x->ch[1], y->ch[1], val, t-1);
        else if(y->ch[0]) dfs2(x->ch[1], y->ch[0], val|(1<<t), t-1);
    }
}

int dfs(Node *x, int t) {
    if(!x) return 0;
    x->siz=dfs(x->ch[0], t-1)+dfs(x->ch[1], t-1)+1;
    if(x->ch[0] && x->ch[1]) {
        nmin=0x7fffffff;
        if(x->ch[0]->siz>x->ch[1]->siz) dfs2(x->ch[1], x->ch[0], (1<<t), t-1);
        else dfs2(x->ch[0], x->ch[1], (1<<t), t-1);
        ans+=nmin;
    }
    return x->siz;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), ini();
    int n, na;
    cin>>n;
    for(int i=0;i<n;i++) cin>>na, ins(na);
    dfs(rt, 30);
    cout<<ans<<endl;
    return 0;
}

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

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • May 2025 1
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 31
    • August 2018 18
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 281
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material