Codeforces 888G. Xor-MST（异或最小生成树）

本文主要是介绍Codeforces 888G. Xor-MST（异或最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given a complete undirected graph with n vertices. A number a i is assigned to each vertex, and the weight of an edge between vertices i and j is equal to a i xor a j.

Calculate the weight of the minimum spanning tree in this graph.

Input
The first line contains n (1 ≤ n ≤ 200000) — the number of vertices in the graph.

The second line contains n integers a 1, a 2, …, a n (0 ≤ a i < 230) — the numbers assigned to the vertices.

Output
Print one number — the weight of the minimum spanning tree in the graph.

Examples
inputCopy
5
1 2 3 4 5
outputCopy
8
inputCopy
4
1 2 3 4
outputCopy
8

思路和代码参考自洛谷上的，因为今天多校来写，又学到新姿势。
https://www.luogu.com.cn/problem/solution/CF888G

题意：
每个点有一个权值，边为两个点的异或值。
这是一张完全图，求MST

思路：
这是一张完全图，当然是不能用kruskal或者prim。
但是最小生成树除了这两个算法，还有一个叫做boruvka的算法，大致思路是维护每个连通块连出的最短边，然后每个连通块择优，选上最短边。

用在本题上，我们可以建立01字典树，那么每次对于连出的0出边和1出边，各有一个连通块，要连通这两个连通块，则需要从左子树（右子树）中枚举一个点，然后再利用01字典树的性质，得到在另一半对应的最小值。

因为对于两个点异或值，肯定是高位相等的越多，值越小，所以从01字典树最高位往下走是符合boruvka算法的

对于每个分出两个子树的点都这样处理，这类似分治的过程，复杂度肯定是够的。

#include<iostream>
#include<vector>
#include<map>
#include <algorithm>
#include <cstdio>
#include <cstring>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 7;int L[maxn * 40],R[maxn * 40];
int ch[maxn * 40][2],tot;
int n,root;
int a[maxn];void Insert(int &now,int x,int dep) {if(!now) now = ++tot;L[now] = min(L[now],x);R[now] = max(R[now],x);if(dep < 0) return;int bit = a[x] >> dep & 1;Insert(ch[now][bit],x,dep - 1);
}ll query(int now,int val,int dep) {if(dep < 0) return 0;int bit = (val >> dep) & 1;if(ch[now][bit]) return query(ch[now][bit],val,dep - 1);return query(ch[now][bit ^ 1],val,dep - 1) + (1 << dep);
}ll dfs(int now,int dep) {if(dep < 0) return 0;if(R[ch[now][0]] && R[ch[now][1]]) {ll mi = INF;for(int i = L[ch[now][0]];i <= R[ch[now][0]];i++) {mi = min(mi,query(ch[now][1],a[i],dep - 1));}return dfs(ch[now][0],dep - 1) + mi + dfs(ch[now][1],dep - 1) + (1 << dep);}if(R[ch[now][0]]) return dfs(ch[now][0],dep - 1);if(R[ch[now][1]]) return dfs(ch[now][1],dep - 1);return 0;
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}sort(a + 1,a + 1 + n);memset(L,0x3f,sizeof(L));for(int i = 1;i <= n;i++) Insert(root, i, 30);printf("%lld\n",dfs(root,30));return 0;
}