ACM-ICPC寒假算法训练2：高级数据结构2：带权并查集练习

本文主要是介绍ACM-ICPC寒假算法训练2：高级数据结构2：带权并查集练习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法设计思路：

这题有个非常有意思的地方：权值是点x到根节点的距离，每次合并的时候，一棵树合并到另一棵树上时，是那种退化的树（所谓一字长蛇阵），所以每次是队列连接，然后是一个队列的队首接到另一个队列的队尾！所以这个时候我们并不知道节点之间的权重更新的情况，莫非更新一次还要去遍历两个队列？？所以我们增加一个数组：cnt[]存储当前元素x作为队首所在的队列的长度！

find：这个不用说，就是:

dis(x, rx) = dis(x, rx) + dis(rx, rx)

由于长度就是那种1、2、3这样子的，所以直接相加

merge：增加一个数组维护队列规模的好处：

假设是px->py

第一步：更新px的状态

dis(px, py) = dis(px, px) + cnt[px] = 0 + cnt[px]

第二步：更新py的队列规模

cnt[py] += cnt[px]（把px的队列全部收编！）

第三步：更新px的队列规模

cnt[px] = 0（也可不这么做，反正也用不到了）px不再是队首，归0

AC代码：

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 3e4 + 5;
int t, p[maxn], dis[maxn], cnt[maxn];
int find(int x){
	if(x == p[x])	return x;
	int r = p[x]; p[x] = find(p[x]);
	dis[x] += dis[r]; 
	return p[x];
}

void merge(int x, int y){
	int px = find(x), py = find(y);
	if(px != py){
		p[px] = py;
		dis[px] += cnt[py];
		cnt[py] += cnt[px];
		cnt[px] = 0;
	}
}

int main(){
	cin >> t;
	for(int i = 1;i <= maxn;i++){
		p[i] = i;
		cnt[i] = 1;
	}
	while(t--){
		char ch; int a, b;
		cin >> ch >> a >> b;
		if('C' == ch){
			if(find(a) == find(b))
				cout << abs(dis[a] - dis[b]) - 1 << endl;
			else
				cout << -1 << endl;
		}
		else
			merge(a, b);
	}
	return 0;
}

这篇关于ACM-ICPC寒假算法训练2：高级数据结构2：带权并查集练习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！