P2024 食物链 题解

· · 题解

题目传送门

在P1196 银河英雄传说 中，我们讲的是用并查集维护一些我们想要的东西。

然后在这一题中，我们来讲讲另一种并查集：扩展域并查集。

扩展域并查集

并查集维护的是一种朋友的朋友是朋友的关系。

但大家也都明白敌人的敌人是朋友，这时候，普通并查集就对这种关系无能为力了。

这时，扩展域并查集诞生了。

就拿刚刚敌人的敌人是朋友为例，我们用 x 表示 x 朋友，x+n 表示 x的敌人，对于x是y的敌人，我们就可以合并 x 和 y+n ， x+n 和 y。

完美！

所以扩展域并查集的核心观点是：用x+n,x+2n...表示x的多种关系。然后用并查集维护同一种关系。

关于扩展域并查集，大家可以先去做做P1525 关押罪犯练练手

解法部分

我们建一个扩展域并查集，x为同类，x+n为食物，x+2n为敌人。

对于每一个X与Y是同类的条件，由下图可以想到：x和y是同类，x+n和y+n是同类，x+2n和y+2n是同类。

对于每一个X吃Y的条件，由下图可以想到：x+n和y是同类,x和y+2n是同类，y+n和x+2n是同类。

题目中说了：食物链是环形的，为了方便理解话成了图中的样子。

那么：怎么判断是不是谎话呢？

首先我们先看到题目给的谎话由几种：

  1. 当前的话与前面的某些真的话冲突，就是假话。
  2. 当前的话中 X 或 Y 比 N 大，就是假话。
  3. 当前的话表示 X 吃 X，就是假话。

对于第2条我们直接判断即可。第3条和第1条我们其实可以合在一起判断。

为啥呢？

你 X 吃 X 不矛盾开什么国际玩笑！

对于 X 和 Y 是同类这条描述：如果 X 和 Y+N 在同一个集合内（Y吃X）或者 X 和 Y+2N 在同一个集合内（X 吃 Y）则该条描述为假话。

对于 X 吃 Y 这条描述：如果 X 和 Y+N 在同一个集合内(Y 吃 X),或者 X 和 Y 在同一个集合(X 和 Y 是同类) 则该条描述为假话。

可以结合上图自行理解。

样例解析：

可能还是有人没听懂。那我讲下样例。

3 5
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1

第 1 条：1 吃 2，所以 4 和 2 是同类，都得被 1 吃，1 和 8 是同类，都要吃 2，因为食物链是环形的，所以 2 的食物会吃 1，2 和 7 都吃 1：

第 2 条：2 吃 3，所以 5 和 3 是同类，都得被 2 吃，9 和 2 是同类，都要吃 3，因为食物链是环形的，所以 3 的食物会吃 2，6 和 8 都吃 2：

第 3 条：3 吃 3，这句话是 X 吃 X 的格式，是谎话。

第 4 条：1 和 3 是同类，但 1 的祖先是 6 ，也就是说 1 被 3 吃，是谎话。

第 5 条：3 吃 1，所以 1 和 6 是同类，都得被 3 吃，7 和 3 是同类，都要吃 1，因为食物链是环形的，所以 1 的食物会吃 3，4 和 9 都吃 2：

至此，有 2 句谎话。

代码

思路部分都讲的差不多了，也就不写注释了

#include<bits/stdc++.h>
using namespace std;
int n,k,fa[300005],ans=0;
int findfa(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=findfa(fa[x]);
} 
//x同类 x+n食物 x+2n敌人 
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++)
        fa[i]=i;
    for(int i=1;i<=k;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(x>n || y>n) {ans++;continue;}
        int fa1=findfa(y),fa2=findfa(y+n),fa3=findfa(y+2*n);
        int fa4=findfa(x),fa5=findfa(x+n),fa6=findfa(x+2*n); 
        if(op==1)
        {
            if(fa1==fa5 || fa1==fa6) ans++;
            else
            {
                if(fa1!=fa4) fa[fa1]=fa4;
                if(fa2!=fa5) fa[fa2]=fa5;
                if(fa3!=fa6) fa[fa3]=fa6;
            }
        }
        else if(op==2)
        {
            if(fa1==fa4 || fa1==fa6) ans++;
            else 
            {
                if(fa1!=fa5) fa[fa1]=fa5;
                if(fa3!=fa4) fa[fa3]=fa4;
                if(fa2!=fa6) fa[fa2]=fa6;
            }
        }
    }
    printf("%d",ans);
    return 0;
}