P2024 [NOI2001]食物链

香风智乃 · 2018-08-02 09:47:35 · 个人记录

https://www.luogu.org/problemnew/show/P2024

并查集 建立补集法

链接1：https://www.luogu.org/blog/Sooke/solution-p2024 （结构严谨）

链接2：https://dankuroto.blog.luogu.org/solution-p2024 （通俗易懂）

以上两篇题解建议配合食用

建立补集法：通常是有几种固定的种类（如本题限定一共3种动物），建立n倍点的并查集（本题为n*3），然后合并时根据题意做n次合并即可。

注意补集之间形成一个环的关系，合并时要注意

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#define rint register int
using namespace std;

inline int getint()
{
    register char c=getchar(); rint x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x;
}

const int maxn=50002;
int fa[maxn*3];//开3倍的数组（包含补集）
int n,m,ans;

inline int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
inline void unity(int x,int y)
{
    int r1=find(x),r2=find(y);
    if(r1!=r2) fa[r1]=r2;
}
//--------普通的并查集----------
int main()
{
    //freopen("P2024.in","r",stdin);
    n=getint(); m=getint();
    rint q1,q2,q3;
    for(rint i=n*3;i>=1;--i) fa[i]=i;
    for(rint i=1;i<=m;++i)
    {
        q1=getint(); q2=getint(); q3=getint();
        if(q2>n||q3>n){++ans; continue;}
        if(q1==1)
        {
            if(find(q2)==find(q3+n)||find(q2)==find(q3+(n<<1))){++ans; continue;}//如果已经存在捕食关系
            unity(q2,q3); unity(q2+n,q3+n); unity(q2+(n<<1),q3+(n<<1)); //同类合并
        }
        else if(q1==2)
        {
            if(q2==q3||find(q2)==find(q3)||find(q2)==find(q3+n)){++ans; continue;} //如果是同类或者已存在相反的捕食关系
            unity(q2+n,q3); unity(q2+(n<<1),q3+n); unity(q2,q3+(n<<1)); //q2的捕食者是q3的同类，所以把他们两个合并，其他也相同
        }
    }
    printf("%d",ans);
    return 0;
}