【数字_ID】POJ-1182-食物链（带权or拆点 并查集）

• 编辑：数字_ID
• 时间：2018年5月22日

1. 写在题前

• 一道非常经典的且有意思的并查集题目，所以打算放上原题，慢慢讲
• 2018西安邀请赛的热身赛有一道类似的，是说，有n个人，逐渐给出k句话，每句话给出i，j，表示ij中有一个是叛徒，问你矛不矛盾，如果矛盾，说出最早出现矛盾的是第几句话，如果不矛盾，给出叛徒的个数可能的最大值，和这道题基本一毛一样

2. 题目

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

3. 关于并查集

• 非常优雅
• 记录每个点的最上面的父亲节点，可以理解为记录每个节点的“祖先”
• 网上教程和例题很多，我就给出一个短小的常规操作好了

void init()
{
    for(int i = 0;i<n;i++)
    {
        fa[i] = i;
    }
}
int find(int x)
{
    return (fa[x] == x)?x:fa[x] = find(fa[x]);  
}

void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
    {
        fa[fx] = fy;
    }
}

4. 关于这道题

• 有两种解法，由于自己做的题少，也是通过这道题第一次接触带权并查集和拆点并查集这两种玩法

1. 带权

• 对于每个节点，给他一个权值，可以用val[]数组保存，用来表示他和父亲的关系，其中，0表示和父亲同类，1表示被父亲吃，2表示吃父亲，为什么这么搞呢？我们可以分析一下这样做，他的两种关系转移特征
  1. 假设A是B的父亲，B是C的父亲，已知A吃B，B吃C，那么A和C的关系是什么呢？
     B是A的儿子同时是C的父亲.png
     A吃B，B吃C，那么val[B] == 1,val[C] == 1,在find过程中会变成B，C同父，C的父亲变了，自然权值也就变了，根据题意，此时是C吃A，val[C] ==2,其实稍微想一下会发现，这个过程中，关系转移方程式val[C] = (val[B]+val[C])%3
  2. 假设BC有相同的父亲A，已知他们和A的关系，求BC的关系 B和C相同父亲.png
     其实此时,BC关系的方程式为(val[B]-val[B]+3)%3
• 知道关系转移式之后，就可以轻松地切这道题了

2. 拆点

• 这个方法理解起来需要一点时间，我觉得网上说的平行宇宙比喻很有意思
• 既然有三种关系，我们就假设有三个平行宇宙
• 如果x吃y，就让宇宙1的x和宇宙2的y归为一类，宇宙2的x和宇宙3的y归为一类，宇宙3的x和宇宙1的y归为一类，相反的，如果宇宙3的x和宇宙1的y是一类，那么就说明宇宙1中x吃y
• 如果x和y同类，就让每个宇宙中的x和y都归为一类
• 利用这个逻辑去判断是否矛盾。比如，如果题目说x和y是同类，但是你发现宇宙2的x和宇宙3的y是一类，也就是你发现在你的记录中x吃y，那么就产生矛盾了，ans++，其他同理

5. 代码

带权代码

#include<iostream>
#include<string.h>
#include<stdio.h>

using namespace std;

const int maxn = 50020;

int fa[maxn],val[maxn];//val数组表示每个节点和其father的关系，0表示同类，1表示被吃，2表示吃
int n,k;
void init()
{
    for(int i = 0;i<n;i++)
    {
        fa[i] = i;
        val[i] = 0;
    }
}
int find(int x)
{
    if(fa[x] == x)return fa[x];
    else
    {
        int temp = fa[x];
        fa[x] = find(fa[x]);
        val[x] = (val[x]+val[temp])%3;
        return fa[x];
    }
}
void merge(int x,int y,int t)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
    {
        fa[fx] = fy;
        val[fx] = (val[y]-val[x]+t+3)%3;        
    }   
}

bool isOK(int x,int y,int t)
{
    if(x>n||y>n)return false;
    if(x == y&&t!=0)return false;
    if(find(x) == find(y))
    {
        return (val[x]-val[y]+3)%3 == t;
    }
    else return true;
}

int main()
{
    scanf("%d%d",&n,&k);
    int ans = 0;
    int x,y,t;
    init();
    while(k--)
    {
        scanf("%d%d%d",&t,&x,&y);
        if(isOK(x,y,t-1))
        {
            merge(x,y,t-1);
        }
        else ans++;
    }
    cout<<ans<<endl;
}

拆点代码

#include<iostream>

using namespace std;

const int maxn = 150020;

int fa[maxn];

int n,k;
void init()
{
    for(int i = 0;i<3*n;i++)
    {
        fa[i] = i;
    }
}
int find(int x)
{
    return (fa[x] == x)?x:fa[x] = find(fa[x]);  
}

void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
    {
        fa[fx] = fy;
    }
}
bool isOK(int x,int y,int t)
{
    if(x == y&&t!=1)return false;
    if(x>n||y>n)return false;
    
    if(t == 1)
    {
        if(find(x) == find(y+n)||find(x) == find(y+2*n))return false;
        else return true;
    }
    else
    {
        if(find(x) == find(y)||find(x) == find(y+2*n))return false;
        else return true;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    int ans = 0;
    init();
    while(k--)
    {
        int x,y,t;
        scanf("%d%d%d",&t,&x,&y);
        if(isOK(x,y,t))
        {
            if(t == 1)
            {
                merge(x,y);
                merge(x+n,y+n);
                merge(x+2*n,y+2*n);
            }
            else
            {
                merge(x,y+n);
                merge(x+n,y+2*n);
                merge(x+2*n,y);
            }
        }
        else ans++; 
    }
    cout<<ans<<endl;    
}