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

一道好题:银河英雄传说 洛谷1196

算法设计思路:

这题有个非常有意思的地方:权值是点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;
}
上一篇:JSON数据的相关应用


下一篇:ACM-ICPC寒假算法训练2:高级数据结构1(并查集):基础并查集