题解 P2024 【食物链】

· · 题解

Update on 21.07.16: 修了挂掉的图

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

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

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

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

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

种类并查集

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

我们用 re[x] 表示编号 i 与父亲节点的权值关系，由于只有三种动物，所以权值也只有三种：

转移时便可以采用对 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，别忘了取模。

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

关于打表，其他题解已经给出详细的过程，这里就不做赘述。

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

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

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

 #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;
}

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