CF888G Xor-MST

Posted on | Edited on | Views:

$Boruvka$ 算法求解最小生成树.

有一张 $n$ 个点的完全图,其中第 $i$ 个点有一个权值 $a_i$ ,两个点 $i,j$ 之间的边权为 $a_i\oplus a_j$ .

需要求出这张完全图的最小生成树的权值.

$n\le 2\times 10^5,0\le a_i<2^{30}$ .

利用 $Boruvka​$ 算法求解.

  • 这个算法需要进行若干轮,初始时每个点是一个独立的连通块.
  • 每一轮中,对于每个连通块,找到边权 $w$ 最小的边 $e=(u,v,w)$ ,满足 $u$ 在该块内,而 $v​$ 不在该块内.
  • 将这些边都加入图中,利用并查集维护连通性.
  • 当加入了 $n-1$ 条边后,就得到了一棵最小生成树.
  • 每轮暴力枚举每条边,而每做一轮,连通块数目至少减少为原来的一半,所以时间复杂度为 $O((m+n)\log n)$ .

这个算法的瓶颈在于对于每个连通块找出连出去的边中,边权最小的那条边.

可以利用 $Trie$ 树优化这个找边过程,时间复杂度优化到 $O(n\log a\log n)$ .

这类套路题大概是每个点有点权,任意两点之间的边权由二者的点权决定,需要求最小生成树.

做法大致都和这道题类似,尝试去优化找最优边的过程.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10,K=30;
const int inf=0x7fffffff;
struct Trie
{
	int idx;
	Trie(){idx=1;}
	int ch[MAXN*K][2],val[MAXN*K],id[MAXN*K];
	void ins(int x,int v,int k)
	{
		int u=1;
		for(int i=K-1;i>=0;--i)
		{
			int c=(x>>i)&1;
			if(!ch[u][c])
				ch[u][c]=++idx;
			u=ch[u][c];
			val[u]+=v;
		}
		id[u]=k;
	}
	int query(int x)
	{
		int u=1;
		for(int i=K-1;i>=0;--i)
		{
			int c=(x>>i)&1;
			if(val[ch[u][c]])
				u=ch[u][c];
			else
				u=ch[u][c^1];
		}
		return id[u];
	}
}T;
int n,m=0,a[MAXN],fa[MAXN],p[MAXN];
int Find(int x)
{
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}
bool cmp(int x,int y)
{
	return fa[x]<fa[y];
}
void init()
{
	for(int i=1;i<=n;++i)
	{
		p[i]=fa[i]=i;
		T.ins(a[i],1,i);
	}
}
pair<int,int> mi[MAXN];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	sort(a+1,a+1+n);
	n=unique(a+1,a+1+n)-a-1;
	init();
	ll ans=0;
	while(m<n-1)
	{
		for(int i=1;i<=n;++i)
			fa[i]=Find(i);
		sort(p+1,p+1+n);
		for(int i=1;i<=n;++i)
			mi[i]=make_pair(i,inf);
		int Fa;
		for(int l=1,r;l<=n;++l)
		{
			Fa=fa[p[l]];
			r=l;
			while(r+1<n && fa[p[r+1]]==Fa)
				++r;
			for(int i=l;i<=r;++i)
				T.ins(a[p[i]],-1,p[i]);
			for(int i=l;i<=r;++i)
			{
				int x=p[i];
				int y=T.query(a[x]);
				if((a[x]^a[y])<mi[Fa].second)
					mi[Fa]=make_pair(y,a[x]^a[y]);	
			}
			for(int i=l;i<=r;++i)
				T.ins(a[p[i]],1,p[i]);
			l=r;
		}
		for(int i=1;i<=n;++i)
		{
			int x=Find(i),y=Find(mi[i].first);
			if(x==y)
				continue;
			fa[x]=y;
			ans+=mi[i].second;
			++m;
		}
	}
	cout<<ans<<endl;
	return 0;
}