[NOI2001]食物链

[NOI2001]食物链

题目大意是肯定能够看得懂的，就是怎么做是个问题而已。。

我的方法是用带权并查集 ，首先我们可以加多一个数组r表示 r和父亲（根） 的关系

详情看代码就懂了

#include<bits/stdc++.h> //a==fa[a]   0    a -> fa[a]  1   a <- fa[a]  2
using namespace std;  //上面就是表示r的三种状态，如果为0就说明和父亲相等，为1就表明可以吃父亲，为2就是被父亲吃。
int fa[],r[],ans,n,m;
int get(int x){
    if(fa[x]==x)    return x;
    int y=fa[x];//记住原来的父亲
    fa[x]=get(fa[x]);//路径压缩
    r[x]=(r[y]+r[x])%;//更新和现在的父亲的关系
    return fa[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++) fa[i]=i;
    for(;m--;){
        int c,x,y;
        scanf("%d%d%d",&c,&x,&y);
        if(x>n||y>n) ans++;
        else
        {
            int xx=get(x),yy=get(y);
            if(xx==yy){
                if(c==&&r[x]!=r[y]) ans++;//就是判断和根的关系十分相同
                if(c==&&(r[x]==r[y]||(r[y]+)%==r[x])) ans++;//判断矛盾关系
            }
            else {
                fa[xx]=yy;//建立关系
                if(c==) r[xx]=(r[y]-r[x]+)%;
                else r[xx]=(r[y]-r[x]+)%;
            }
        }
    }
    printf("%d",ans);
    return ;
}
           

其实还有一种方法，就是反正我们不确定每个动物是属于A、B还是C，我们就每种情况都考虑进去（开3倍空间)。假设是1操作，输入的x和y，我们就把每个种类的x和连起来,成为一个集合（并查集),如果是2操作就把三种情况：1、x是A y是B 2、x是B y是C 3、x是C y是A

分别连起来，然后判断矛盾就很简单了。

看代码吧

#include<bits/stdc++.h>
using namespace std;
int fa[*],n,m,ans;
int get(int x){
    return x==fa[x]? x:(fa[x]=get(fa[x]));//简单的并查集
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=;i<=*n;i++) fa[i]=i;
    for(;m--;){
        int c,x,y;
        scanf("%d%d%d",&c,&x,&y);
        if(x>n||y>n) ans++;//不属于这条食物链
        else
        if(c==){
            if(get(x+n)==get(y)||get(x)==get(y+n)) ans++;//如果x是y的猎物或y是x的猎物就矛盾
            else fa[get(x)]=fa[get(y)],fa[get(x+n)]=fa[get(y+n)],fa[get(x+*n)]=fa[get(y+*n)];//就是上面讲的 
        }
        else{
            if(get(x)==get(y)||get(x+n)==get(y)) ans++; //如果x和y同类或x是y的猎物就矛盾
            else fa[get(x)]=fa[get(y+n)],fa[get(x+n)]=fa[get(y+*n)],fa[get(x+*n)]=fa[get(y)];//就是上面讲的+1
        }
    } 
    printf("%d",ans);
    return ;
}
           

做完这题感觉对并查集的理解又深了一些