本文共 2287 字，大约阅读时间需要 7 分钟。

今天练习带权并查集

题1 ：

题意及算法分析：

如果a和b在一棵树上，则他们之间有关系，如果dis[a]与dis[b]同为0 或 1，则是同一个帮派，否则是不同的帮派，如果不在一棵树上，则状态不明确。

AC代码：

#include 
   
    #include 
    
     const int maxn = 1e5 + 5;int n, m, t, p[maxn], dis[maxn];void init(){   	for(int i = 1;i <= n;i++){   		p[i] = i;		dis[i] = 0;	}}int find(int x){   	if(x == p[x])		return x;	int r = p[x]; p[x] = find(p[x]);	dis[x] = (dis[x] + dis[r]) % 2;	return p[x];}void merge(int x, int y){   	int px = find(x), py = find(y);	if(px != py){   		p[px] = py;		dis[px] = (dis[y] - dis[x] + 1) % 2;	}}int main(){   	scanf("%d",&t);	while(t--){   		scanf("%d %d",&n,&m);		init();		while(m--){   			char ch;			int a, b;			getchar();			scanf("%c %d %d",&ch,&a,&b);			if('D' == ch)				merge(a, b);			else{   				if(find(a) == find(b)){   					if(dis[a] == dis[b])						printf("In the same gang.\n");					else						printf("In different gangs.\n");				}				else					printf("Not sure yet.\n");			}		}	}	return 0;}
    
   

题二：

题意及算法分析：

有三个种类，则dis(x, y)分三类：

0：他们是同类 1：x吃y 2：x被y吃

这样分类有个好处：如果是同类：cmd = 1(1 - 1 = 0)，x被y吃：cmd = 2(2 - 1 = 1)

这样就可以得到：x与y的状态可以由cmd直接得出。

最初的权值：

因为最开始，自己和自己当然是一类生物，所以初始化的时候都是0（同类）

Find中的权值更新：

因为我们最终合并两棵树是合并他们的根，于是要得到dis(x, rx)

dis(x, rx) = (dis(x, rx) + dis(rx, rx)) % 3 也就是：dis[x] = (dis[x] + dis[r]) % 3

Union的权值更新：

我们规定更新的方向：p[px] = py

也就是把py当作新的树根，把px接到py的孩子处 因为我更新的对象是x和y，所以需要通过关系：dis(x, y)来更新dis(rx, ry) 我们已经根据上面的讲述，得到dis(x, y) = cmd - 1 x->rx, y->ry, rx->ry 根据这个向量关系可以得到： dis(rx, ry) = dis(x, y) + dis(x, rx) - dis(y, ry) 所以代码就是： dis[px] = (cmd - 1 + dis[x] - dis[y] + 3) % 3 这里加3的原因是维护非负整数

AC代码：

#include 
   
    const int maxn = 5e4 + 5;int n, k, p[maxn], dis[maxn], ans;int find(int x){   	if(x == p[x])	return x;	int r = p[x]; p[x] = find(p[x]);	dis[x] = (dis[x] + dis[r]) % 3;	return p[x];}void merge(int type, int x, int y){   	int px = find(x), py = find(y);	if(px != py){   		p[px] = py;		dis[px] = (type - 1 + dis[y] - dis[x] + 3) % 3;	}}int main(){   	scanf("%d %d",&n, &k);	for(int i = 1;i <= n;i++)	p[i] = i, dis[i] = 0;	while(k--){   		int cmd, a, b;		scanf("%d %d %d",&cmd, &a, &b);		if(a > n || b > n || (2 == cmd && a == b))			ans++;		else if(find(a) == find(b)){   			if(1 == cmd && dis[a] != dis[b])				ans++;			if(2 == cmd && dis[a] != (dis[b] + 1) % 3)				ans++;		}		else			merge(cmd, a, b);	}	printf("%d", ans);	return 0;}