CodeForces 888G Xor-MST|trie+MST

题目链接
为方便描述，下文将使用最小生成树的缩写MST Minimum Spanning Tree

题目大意：

（搬运自Luogu）
给定 (n) 个结点的无向完全图。每个点有一个点权为 (a_i) 。连接 (i) 号结点和 (j) 号结点的边的边权为 (a_ioplus a_j)。
求这个图的 MST 的权值。
(1≤n≤2×10^5 ，0le a_i< 2^{30}) ，时限2S

题目思路：

很巧妙的思路。

先来介绍一下最小生成树除了Kruskal和Prim的较少运用的第三种解法——Boruvka。这个算法常用于完全图的MST问题（未经验证，欢迎交流）。可以将这个算法理解为：先将每个点作为一个联通块，每次用各个联通块向块外的最小边权使不同连通块合并，并将其加入边集。最后得到的边集即为最小生成树。该算法的时间复杂度为 (O(mlogn)) ，其中 (m) 为边数，(n) 为点数。
以下这一张图片解释了算法过程。
CodeForces 888G Xor-MST|trie+MST
（来源：OI-wiki / *）
回到本题，由于本题与异或有关，我们可以考虑运用线性基或01trie。本题考虑使用01trie。
在Trie上，有 (n) 个不同的数，则意味着有 (n-1) 个点会同时有左右儿子。根据Boruvka算法的思想，我们先对每个数作为一个联通块。要对两个联通块合并，则是对于这些同时拥有左右儿子的节点的左右儿子合并。因为算法要求每次用最小边权的边合并，而这些节点是两个联通块的最深LCA。由trie的结构可知，对它们来说，上面更高的位是相同的，不会对异或产生贡献的。如果不是左右联通块先合并，而是与其他联通块合并，那么更高的位将对异或产生贡献，边权显然会更大，不合题意。此时考虑边权最小的情况，就是更低位的异或值也要尽量少，那么向两棵子树尽量同时走相同的0/1即可。
另外，本题并未保证 (a_i) 互不相同，但实际上，相同的 (a_i) 将会按一个点处理，对结果不会产生任何影响。

上代码，最高546ms，对本题来说绰绰有余。

#include<bits/stdc++.h>
using namespace std;
int g,n,X;
long long ans;
struct trie
{
	int a[2],num;
}t[6001000];
void addtrie(int x,int w)
{
	if (w==-1) return ;
	if ((X>>w)&1)
	{
		if (!t[x].a[1])
		{
			t[x].a[1]=++g;
		}
		addtrie(t[x].a[1],w-1);
	}
	else
	{
		if (!t[x].a[0])
		{
			t[x].a[0]=++g;
		}
		addtrie(t[x].a[0],w-1);
	}
}//trie的插入数
int findmin(int w,int x,int y,int val)
{
	if (w<=-1) return val;
	int gx=1<<30,gy=1<<30;
	if (t[x].a[0])
	{
		if (t[y].a[0]) gx=findmin(w-1,t[x].a[0],t[y].a[0],val);
		else if (t[y].a[1]) gx=findmin(w-1,t[x].a[0],t[y].a[1],val+(1<<w));
	}
	if (t[x].a[1])
	{
		if (t[y].a[1]) gy=findmin(w-1,t[x].a[1],t[y].a[1],val);
			else if (t[y].a[0]) gy=findmin(w-1,t[x].a[1],t[y].a[0],val+(1<<w));	
	}
	return min(gx,gy);
}//左右儿子中的异或最小值，尽量两边同时往0/1跳
void check(int x,int y)
{
	if (y==-1) return ;	
	if (t[x].a[0]) check(t[x].a[0],y-1);
	if (t[x].a[1]) check(t[x].a[1],y-1);
	if (t[x].a[0]&&t[x].a[1]) 
	{
		ans+=findmin(y-1,t[x].a[0],t[x].a[1],1<<y); 		
	}
}//寻找左右儿子
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>X;
		addtrie(0,30);
	}
	check(0,30);
	cout<<ans<<endl;
	return 0;
}

CodeForces 888G Xor-MST|trie+MST

相关推荐