站外题求助（最小生成树+倍增并查集）

给定一张 n 个点的完全图，和序列

[a_3,a_4,...,a_{2n-1}]

。

点的编号为 1∼n，对于两个点

i,j

(i不等于j)，它们之间的边权为

a_{i+j}

。

请你求解这张图的最小生成树，你只需要给出最小生成树的边权和即可。

数据范围:

对于 20% 的测试点： n ≤ 1000。

对于 30% 的测试点： n ≤ 10000。

对于另外 20% 的测试点：

a_i

在

[1,10^9]

中均匀随机生成。

对于所有测试点：

1≤n≤2 \times 10^5,1≤a_i≤10^9

。

我的思路如下：

称两端节点编号和相等的边为同一种边。

先用结构体存下每种边的边权和节点编号和，按边权升序排序。

考虑在Kruskal基础上优化。

若按传统并查集的方式，对于每种边，要枚举每一对节点尝试连接，复杂度

O(n^2)

不难发现，对于节点编号和为id的这一种边，我们需要尝试连接的节点有(l,r),(l+1,r-1),......

想到用区间的合并代替一系列连续点对的合并。

具体地，开 log 层并查集，每层开 2n 个点，前 n 个表示 [i,i+2^k-1]，后 n 个表示 [i-2^k+1,i] 的 reverse

每次合并同层的两个区间，如果它们不在一个集合，就递归左右区间分别合并，直到最底层的单点时，可以统计答案

这样每层一共只有 n 次合并。

CPP


int find(int deep,int x){
	return fa[deep][x]==x?x:fa[deep][x]=find(deep,fa[deep][x]);
}

void hb(int L,int R,int k){
	int fx=find(k,L),fy=find(k,2*n+1-R);
	if(fx!=fy){
		fa[k][fy]=fx;
		if(k) hb(L,R,k-1),hb(L+(1<<k-1),R-(1<<k-1),k-1);
		else cnt++,ans+=1ll*v[L+R];
	}
}

void merge(int l,int r){
	int ed=l+r>>1;
	ed+=l+r&1;
	int maxi=log2(ed-l);
	for(int i=maxi;i>=0;i--){
		if(ed-l&(1<<i)){
			hb(l,r,i);
			l+=(1<<i);
			r-=(1<<i);
		}
	}
}

具体实现的核心函数如上。

由于本人太弱，不知是否有大佬帮忙看看这样的思路是否可行。

以及，这题所在的题目集已关闭，我没法再提交代码验证正确性。不知其他各平台是否有类似的题。

感谢！

站外题求助（最小生成树+倍增并查集）

讨论操作

回复

相关推荐

站外题求助（最小生成树+倍增并查集）