poj 1182 食物链

并！查！集！好！难！啊！

看了两天才看懂我对自己的智商完全没自信了╭(╯^╰)╮

所谓的种类并查集。。一个集合代表一类，求解各类之间的关系问题。

对于本题，

首先，集合里的每个点我们都记录它与它这个集合(或者称为子树)的根结点的相对关系rank。0表示它与根结点为同类，1表示它吃根结点，2表示它被根结点吃。

0,1,2也是距离根节点的具体，rank这个树最多三层，每一层是同类的集合。

题目要判断输入的关系是否合法，可以发现，

1、若两点都没出现过，则合法，肯定啊

2、若出现过某一点a，则若d=1，添加b到a的同类集合，若d=2，则添加b到a的对应关系位置集合

也就是，若有点是第一次出现，一定是合法的，直接进行merge。

3、当两点都出现过，则要判断他们的关系是否合法，利用我们的rank关系就可以知道

若d=1，则a b必须在同一位置，即rank相等时，合法。

若d=2，则a-b=1或-2时合法，

总之，可以用不知道哪个大牛第一个推出来的公式，

按(rank[a]-rank[b]+3)%3!=d-1 判断，一步到位。

以上是总体思路。对于如何merge，更新rank又是个问题

合并时，由于rank这个就三层，0,1,2，0是根，跟上面判断合法是一个道理，也可以用上面那个公式得到。

更新rank啊这个我就更想不到了，直接在root里面更新自己到根的rank，比较好理解。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

int r[50005],n,k,d,ans,rank[50005];

int root(int a)
{
    if(r[a]==a) return a;
    int tmp=r[a];
    r[a]=root(r[a]);
    rank[a]=(rank[a]+rank[tmp])%3;
    return r[a];
}

void merge(int a,int b)
{
    int ra,rb;
    ra=root(a);
    rb=root(b);
    r[ra]=rb;
    rank[ra]=(rank[b]-rank[a]+2+d)%3;
}

int main()
{
    int i,a,b,ra,rb;
    scanf("%d%d",&n,&k);
    ans=0;
    for(i=1;i<=n;i++)
        r[i]=i;
    memset(rank,0,sizeof rank);

    while(k--)
    {
        scanf("%d%d%d",&d,&a,&b);
        if(a>n||b>n||(a==b&&d==2))
        {
            ans++;
            continue;
        }
        ra=root(a);
        rb=root(b);
        if(ra==rb)
        {
            if((rank[a]-rank[b]+3)%3!=d-1)
                ans++;
        }
        else
            merge(a,b);
    }
    printf("%d\n",ans);
    return 0;
}

poj 1182 食物链,布布扣,bubuko.com

poj 1182 食物链

原文：http://blog.csdn.net/u011032846/article/details/20653045