[NOI2001]食物链

发表于 | 更新于 | 分类于 | 阅读次数：

开三个并查集感觉太作弊了于是学了下带权并查集，写篇题解巩固一下_(:з」∠)_。

上网大概搜了下，对带权并查集的诠释是这样的：

在对并查集进行路径压缩和合并操作时，这些权值具有一定属性，即可将他们与父节点的关系，变化为与所在树的根结点关系。

也就是说，权值代表着当前节点与父节点的某种关系（即使路径压缩了也是这样），通过两者关系，也可以将同一棵树下两个节点的关系表示出来。

而P2024《食物链》这道题，又属于加权并查集下的分支：

种类并查集

由题意得，动物一共只有A,B,C三种，也就是说只要确定了一种动物的种类和他们的关系（即权值），其他的动物的种类也就知道了。

我们用re数组表示编号i与父亲节点的权值关系，由于只有三种动物，所以权值也只有三种：0–>同种动物，1–>捕食关系，2–>被捕食关系，转移时便可以采用对3取模来实现。（初始化为0，即自己与自己为同种动物）

那么第一个问题，就是如何在查找与合并时转移这种权值？

1.合并：并查集合并的本质就是一棵树认另一棵树做父亲，把树根相连即可，但是能否也把权值直接赋值呢（比如1操作就直接赋值为1)？ 当然不行，因为给你的a,b是树下节点，还有考虑各自与树根的关系。
也就说，推出A,B各自与根的关系，就可以实现树根权值的连接了。

设F1与F2分别为A,B的根，两者权值关系为re[F1]，A与F1的权值关系是re[A]，B与F2的权值关系是re[B]，A与B的权值关系为x。

由图得，re[f1]=x+re[b]-re[a]

由于可能会造成re[b]-re[a]<0的情况，所以加3再对三取模。又因为x已知为0或1（要么是同种动物，要么是捕食关系），所以最终结果为：

re[f1]=(re[b]-re[a]+3)%3或re[f1]=(1+re[b]-re[a]+3)%3;

2.查找（路径压缩）：路径压缩就是在搜索的时候找到最远的祖先，然后将父亲节点赋值，对于权值而言，就是找出权值与最远祖先之前所有边权传递的过程，找出节点与父亲节点的关系，依次传递即可。

设在同一树内，3号节点父亲是2号，2号父亲是根1号。与父亲的关系依次为re[3]，re[2]，路径压缩后权值为re[3]撇。

显然，re[3]撇=(re[3]+re[2])%3，别忘了取模。

当然不会数学推得话打表也是好方法，本蒟蒻就是打完表水过题再数学证明的_(:з」∠)_。

这两式子一出来，题目就好做多了（我还是因为板子打错了改个近一小时）。

根据题目我们还可以确定：判断两点的关系是否正确必须要在同一棵树下，反之则一定正确。（因为如果是两棵树，两点的关系就不能确定了。）

然后一些小问题又没啥好说了，贴上丑陋的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 #include <iostream>  //带权并查集 题解 
using namespace std;
int f[100000],re[100000];  //0-->同种动物，1-->捕食关系，2-->被捕食关系。
int n,m,a,b,p,ans=0;

int find(int a)
{
	int fa=f[a];
	if (a!=fa) {
		f[a]=find(fa);
		re[a]=(re[a]+re[fa])%3;   
		return f[a];
	}
	else return fa;
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) f[i]=i,re[i]=0;
	for (int i=1;i<=m;i++)
	{
		cin>>p>>a>>b;
		if ((a>n||b>n)||(p==2&&a==b)) {   //两种白痴情况 
			ans++; continue;
		}
		if (p==1)  //对关系1讨论 
		{
			int f1=find(a),f2=find(b);
			if (f1==f2&&re[a]!=re[b])  //判断是否在同一棵树及两者是否为同种动物。 
			{
//				cout<<"YES?"<<endl; 
				ans++; continue;
			}
			else if(f1!=f2)
			{
//				cout<<a<<" "<<re[a]<<" "<<b<<" "<<re[b]<<endl;
				f[f1]=f2; re[f1]=(3-re[a]+re[b])%3;   //合并 
			}
		}
		if (p==2)  //对关系2讨论 
		{
			int f1=find(a),f2=find(b);
			if (f1==f2) 
			{
				int rela=(re[a]-re[b]+3)%3;  //用两个节点与父亲的关系推出两者关系 
//				cout<<f1<<" "<<re[a]<<" "<<re[b]<<" "<<rela<<endl;
				if (rela!=1) {
//					cout<<"HERE?"<<endl;
					ans++; continue;
				}
			}
			else {
				int f1=find(a),f2=find(b);
				f[f1]=f2; re[f1]=(3-re[a]+re[b]+1)%3;   //合并 
			}
		}
	}
//	for (int i=1;i<=n;i++)
	//cout<<f[i]<<" "<<re[i]<<endl;
	cout<<ans<<endl;
	return 0;
}

大概就是这样了，如果我有啥理解错误的地方欢迎指正_(:з」∠)_