MinamiMelon
0%

Borůvka’s algorithm与位运算最小生成树（异或最小生成树，AND最小生成树）

发表于 更新于

Borůvka’s algorithm

最初每个点是孤立点。从所有当前的连通块向其他连通块扩展出最小边，直到只剩一个连通块。

时间复杂度\(O(E\log V)\) 

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
const int N=5005,M=2e5+5;
struct Edge{
	int f,t,v;
}e[M];
int fa[N],lk[N],cpt[N],n,m; //cpt cheapest 子树中最小的边权 
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);};

int Boruvka(){
	int ans=0;
	for(int i=1;i<=n;++i) fa[i]=i;
	int t=n;
	while(t>1){
		for(int i=1;i<=n;++i) lk[i]=0;
		int cnt=0;
		for(int i=1;i<=m;++i){
			int x=find(e[i].f),y=find(e[i].t);
			if(x!=y){
				++cnt;
				if(!lk[x]||cpt[x]>e[i].v) lk[x]=y,cpt[x]=e[i].v;
				if(!lk[y]||cpt[y]>e[i].v) lk[y]=x,cpt[y]=e[i].v;
				//lk[i]: 在本轮连边中 i子树连向哪棵子树 
			}
		}
		if(!cnt) return -1;//图不联通 
		for(int i=1;i<=n;++i){
			if(fa[i]==i){
				fa[find(lk[i])]=i;
				ans+=cpt[i];
				--t;
			}
		}
	}
	return ans;
}

异或最小生成树

给每一个点一个点权，连接两个点\(i,j\)的边的边权为\(a_i\) xor \(a_j\)，求这张图上的最小生成树。

我们怎么快速找到连通块外的最近点（异或值最小的点）呢，这时我们就需要0/1字典树了。

我们可以建立一个全局字典树包含所有的点权，然后对每个连通块都维护一个单独的字典树，每个字典树中包含了这个连通块中的所有点权。

每次查询某个点\(a_i\)的最近点的时候，我们从高位到低位比较，假设当前在第\(i\)位，且\(a_i\)的第\(i\)位上的值为\(b\)，如果连通块外有\(i\)位也为\(b\)的数字（说明\(b\)方向上，全局字典树的size大于当前连通块字典树的size），我们必然选择同为\(b\)的数字，我们在两棵字典树的位置都往\(b\)方向转移。如果没有，我们便在字典树上的位置便要向\(b\) \(xor\) \(1\)的方向转移，结果值就要加上\(2^i\)。

参考：https://zhuanlan.zhihu.com/p/164633727

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
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int t[2][N*60],siz[N*60],val[N*60],root[N];
int cnd;
typedef pair<int,int> pii;
void insert(int u,int x,int i){
	bool b;
	++siz[u];
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]) t[b][u]=++cnd;
		u=t[b][u];
		++siz[u];
	}
	val[u]=i;
}
pii query(int rt,int lt,int x){
	int ans=0;
	for(int i=30;i>=0;--i){//从高位到低位贪心 
		bool b=x>>i&1;
		int sr=t[b][rt]?siz[t[b][rt]]:0;
		int sl=t[b][lt]?siz[t[b][lt]]:0;
		if(sr>sl){//全局的字典树大于当前的字典树 
			rt=t[b][rt];////可以走与x的第i位相同的 
			lt=t[b][lt];
		}else{//不得不走与x的第i位相异的 
			ans+=(1<<i);//当前位对答案贡献 
			rt=t[b^1][rt];
			lt=t[b^1][lt];
		}
	}
	return pii(ans,val[rt]);
}
void merge(int &x,int y){
	if(x==0||y==0){
		x=x+y;
		return;
	}
	merge(t[0][x],t[0][y]);
	merge(t[1][x],t[1][y]);
	siz[x]+=siz[y];
	val[x]=max(val[x],val[y]);
}
int fa[N],lk[N],cpt[N],n,m,a[N]; //cpt cheapest 子树中最小的边权 
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);};

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		fa[i]=i;
		root[i]=i;
	}
	root[0]=n+1;
	cnd=n+1;
	sort(a+1,a+n+1);
	n=unique(a+1,a+n+1)-a-1;//相同的数可以事先用边权为0的边连起来 
	for(int i=1;i<=n;++i){
		insert(root[0],a[i],i);
		insert(root[i],a[i],i);
	}
	int t=n;
	long long ans=0;
	while(t>1){
		for(int i=1;i<=n;++i) lk[i]=0;
		for(int i=1;i<=n;++i){
			int x=find(i);
			pii tmp=query(root[0],root[x],a[i]);
			int w=tmp.first,y=find(tmp.second);
			if(x!=y){
				if(!lk[x]||cpt[x]>w) lk[x]=y,cpt[x]=w;
				if(!lk[y]||cpt[y]>w) lk[y]=x,cpt[y]=w;
			}
		}
		for(int i=1;i<=n;++i){
			if(fa[i]==i){
				int fi=find(lk[i]);
				fa[fi]=i;
				merge(root[i],root[fi]);
				ans+=cpt[i];
				--t;
			}
		}
	}
	printf("%lld",ans); 
	return 0;
}

The 2020 ICPC Asia Macau Regional Contest

C Club Assignment

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<bits/stdc++.h>
using namespace std;

const int N=500000+5;
int t[2][N*60],siz[N*60],val[N*60],root[N];
int cnd;
typedef pair<int,int> pii;
void insert(int u,int x,int i){
	bool b;
	++siz[u];
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]) t[b][u]=++cnd;
		u=t[b][u];
		++siz[u];
	}
	val[u]=i;
}
pii query(int rt,int lt,int x){
	int ans=0;
	for(int i=30;~i;--i){
		bool b=x>>i&1;
		int sr=t[b][rt]?siz[t[b][rt]]:0;
		int sl=t[b][lt]?siz[t[b][lt]]:0;
		if(sr>sl){
			rt=t[b][rt];
			lt=t[b][lt];
		}else{
			ans+=(1<<i);
			rt=t[b^1][rt];
			lt=t[b^1][lt];
		}
	}
	return pii(ans,val[rt]);
}
void merge(int &x,int y){
	if(x==0||y==0){
		x=x+y;
		return ;
	}
	merge(t[0][x],t[0][y]);
	merge(t[1][x],t[1][y]);
	siz[x]+=siz[y];
	val[x]=max(val[x],val[y]);
}
int fa[N],lk[N],cpt[N],n,m,a[N],ff[N*2],ans[N];
pii b[N],lp[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int ffd(int x){
	return ff[x]==x?x:ff[x]=ffd(ff[x]);
}
void uni(int x,int y){
	x=ffd(x),y=ffd(y);
	if(x!=y){
		ff[x]=y;
	}
}
void init(){
	//init start 
	for(int i=1;i<=cnd;++i){
		siz[i]=0;
		t[0][i]=t[1][i]=0;
		val[i]=0;
	}
	cnd=0;
}

int que(int u,int x){
	if(!siz[u]) return 2e9;
	bool b;
	int ans=0;
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]){
			ans|=(1<<i);
			u=t[b^1][u];
		}else{
			u=t[b][u];
		}
	}
	return ans;
}

void ins(int u,int x){
	bool b;
	++siz[u];
	for(int i=30;~i;--i){
		b=x>>i&1;
		if(!t[b][u]) t[b][u]=++cnd;
		u=t[b][u];
		++siz[u];
	}
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			b[i].first=a[i];
			b[i].second=i;
			fa[i]=i;
			root[i]=i;
		}
		root[0]=n+1;
		cnd=n+1;
		sort(a+1,a+n+1);
		int nn=n;
		sort(b+1,b+nn+1);
		n=unique(a+1,a+n+1)-a-1;
		for(int i=1;i<=n;++i){
			insert(root[0],a[i],i);
			insert(root[i],a[i],i);
		}
		int t=n;
		//int as=0;
		for(int i=1;i<=(n<<1);++i){
			ff[i]=i;
		}
		while(t>1){
			for(int i=1;i<=n;++i) lk[i]=0,lp[i]=pii(0,0);
			for(int i=1;i<=n;++i){
				int x=find(i);
				pii tmp=query(root[0],root[x],a[i]);
				int w=tmp.first,y=find(tmp.second);
				if(x!=y){
					if(!lk[x]||cpt[x]>w) lk[x]=y,lp[x]=pii(tmp.second,i),cpt[x]=w;
					if(!lk[x]||cpt[y]>w) lk[y]=x,lp[y]=pii(i,tmp.second),cpt[y]=w;
				}
			}
			for(int i=1;i<=n;++i){
				if(fa[i]==i){
					int fi=find(lk[i]);
					fa[fi]=i;
					merge(root[i],root[fi]);
				//	cout<<lp[i].first<<"to"<<lp[i].second<<' '<<cpt[i]<<endl;
					uni(lp[i].first,lp[i].second+n);
					uni(lp[i].first+n,lp[i].second);
				//	as+=cpt[i];
					--t;
				}
			}
		}
	//	cout<<"!!!"<<as<<endl;
		int p=1,ft=0,nt=0;
		int c1=++cnd,c2=++cnd,a1=2e9,a2=2e9;
		for(int i=1;i<=n;++i){
			int now=ffd(i);
			if(!ft){
				ft=now;
			}else if(!nt){
				nt=now;
			}
			if(now==ft){
				ans[b[p].second]=1;
				a1=min(a1,que(c1,b[p].first));
				ins(c1,b[p++].first);
				while(b[p].first==a[i]){
					ans[b[p].second]=0;
					a2=min(a2,que(c2,b[p].first));
					ins(c2,b[p++].first);
				}
			}else{
				ans[b[p].second]=0;
				a2=min(a2,que(c2,b[p].first));
				ins(c2,b[p++].first);
				while(b[p].first==a[i]){
					ans[b[p].second]=1;
					a1=min(a1,que(c1,b[p].first));
					ins(c1,b[p++].first);
				}
			}
		}
	//	printf("%d %d\n",a1,a2);
		printf("%d\n",min(a1,a2));
		for(int i=1;i<=nn;++i){
			printf("%d",ans[i]+1);
		}
		puts("");
		init();
	}
	return 0;
}