题解 P2024 【食物链】
天泽龟
2018-06-29 02:35:33
Update on 21.07.16: 修了挂掉的图
开三个并查集感觉太作弊了于是学了下**带权并查集**，写篇题解巩固一下_(:з」∠)_。
上网大概搜了下，对带权并查集的诠释是这样的：
>在对并查集进行路径压缩和合并操作时，这些权值具有一定属性，即可将他们与父节点的关系，变化为与所在树的根结点关系。
也就是说，权值代表着**当前节点与父节点的某种关系（即使路径压缩了也是这样）**，通过两者关系，也可以将同一棵树下两个节点的关系表示出来。
------------
而P2024《食物链》这道题，又属于加权并查集下的分支：
### 种类并查集
由题意得，动物一共只有 A,B,C 三种，**也就是说只要确定了一种动物的种类和他们的关系（即权值），其他的动物的种类也就知道了。**
我们用 $re[x]$ 表示编号 $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) \bmod 3$$
或
$$re[f1]=(1+re[b]-re[a]+3) \bmod 3$$
**2.查找（路径压缩）**：路径压缩就是在搜索的时候找到最远的祖先，然后将父亲节点赋值，对于权值而言，就是找出权值与最远祖先之前所有边权传递的过程，找出节点与父亲节点的关系，依次传递即可。
设在同一树内，$3$ 号节点父亲是 $2$ 号，$2$ 号父亲是根 $1$ 号。与父亲的关系依次为 $re[3],re[2]$ ，路径压缩后权值为 $re[3]'$ 。
显然，$re[3]'=(re[3]+re[2]) \bmod3$，别忘了取模。
当然不会数学推得话**打表**也是好方法，本蒟蒻就是打完表水过题再数学证明的_(:з」∠)_。
关于打表，其他题解已经给出详细的过程，这里就不做赘述。
------------
这两式子一出来，题目就好做多了 ~~（我还是因为板子打错了改个近一小时）~~。
根据题目我们还可以确定：判断两点的关系是否正确必须要在同一棵树下，反之则一定正确。（因为如果是两棵树，两点的关系就不能确定了。）
然后一些小问题又没啥好说了，贴上丑陋的代码：
```cpp
#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]) //判断是否在同一棵树及两者是否为同种动物。
{
ans++; continue;
}
else if(f1!=f2)
{
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; //用两个节点与父亲的关系推出两者关系
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; //合并
}
}
}
cout<<ans<<endl;
return 0;
}
```
大概就是这样了，如果我有啥理解错误的地方欢迎指正_(:з」∠)_