MENU

POJ1182 食物链(种类并查集)

2018 年 04 月 19 日 • 阅读: 1543 • 数据结构阅读设置

食物链

  • Time Limit: 1000MS
  • Memory Limit: 10000K
  • Total Submissions: 85027
  • Accepted: 25416

Description

动物王国中有三类动物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),输出假话的总数。

Input

第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。Output只有一个整数,表示假话的数目。

Sample Input

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

Sample Output

3

Source

Noi 01

题意

中文题面,意思很清晰。判断假话的数量。

题解

使用向量关系来维护并查集的合并更新操作。具体参考疯狂的小牛和讲解和驱动幽灵百鬼夜行小肆的讲解,非常详细。

假设有$x$和它的父节点$root[x]$,$relation[x]$表示$x$与$root[x]$的关系,$y$与$root[y]$同,(简写为$rel[x]$,$rel[y]$)

  • relation[x] = 0,表示x与root[x]是同类
  • relation[x] = 1,表示root[x]吃x
  • relation[x] = 2,表示x吃root[x]

假设有向量$x \rightarrow y$(这里x为父节点,y为子节点)

  • 当$x \rightarrow y$的偏移量为0,即rel[y] = 0时,x与y为同类
  • 当$x \rightarrow y$的偏移量为1,即rel[y] = 1时,x吃y
  • 当$x \rightarrow y$的偏移量为2,即rel[y] = 2时,y吃x

那么$x \rightarrow y$的偏移量就相当于题目中的$d-1$,$d=2$时$x$吃$y$,$d=1$时$x$和$y$为同类。

在进行合并操作时,我们把$root[y]$合并到$root[x]$上,让$root[x]$作为父节点,那么怎么更新它们之间的关系呢?这个时候,“向量”就派上了用场。

  • $root[x] \rightarrow root[y] = root[x] \rightarrow x + x \rightarrow y + y \rightarrow root[y]$
  • $rel[root[y]] = (rel[x] + (d - 1) + 3 - rel[y]) \% 3$

其中$\%3$为了保证结果在0到2之间,$y \rightarrow root[y]$的偏移值为$3 - rel[y]$。

在寻找根节点的路径压缩过程中$x$与其祖父节点$rootx[x]$之间的关系更新为$rel[x] = (rel[x] + rel[root[x]]) \% 3$

最后判断的时候,如果root[x]!=root[y],则合并;如果相等,表明x与y的父亲是同一个,那么:

  • 当d = 1时只需要判断rel[x]是否等于rel[y]
  • 当d = 2时判断x和y之间的关系与前面已有的是否矛盾,$x \rightarrow y = x \rightarrow root[x] + root[x] \rightarrow y$,即$ (3 - rel[x] + rel[y]) \% 3 == d - 1$是否正确

具体实现看代码。

代码

  • 版本一
StatusAccepted
Time188ms
Memory4824kB
Length1354
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int F[maxn];
int rel[maxn];

int find(int x)
{
    if (x == F[x])
        return x;
    int tmp = find(F[x]);
    rel[x] = (rel[x] + rel[F[x]]) % 3;
    F[x] = tmp;
    return F[x];
}

int main()
{
    int n, m, sum;
    int d, x, y;
    scanf("%d%d", &n, &m);
    sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        F[i] = i;
        rel[i] = 0;
    }
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n)
        {
            sum++;
            continue;
        }
        if (d == 2 && x == y)
        {
            sum++;
            continue;
        }
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty)
        {
            F[rooty] = rootx;
            rel[rooty] = (rel[x] + d - 1 + 3 - rel[y]) % 3;
        }
        else
        {
            if (d == 1 && rel[x] != rel[y])
                sum++;
            else if (d == 2 && ((3 - rel[x] + rel[y]) % 3 != (d-1)))
                sum++;
        }
    }
    printf("%d\n", sum);
    return 0;
}
  • 版本二
StatusAccepted
Time195ms
Memory4824kB
Length2607
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int n, m, sum;
int d, x, y;

struct Node
{
    int pre;
    int rel;
}node[maxn];

void init()
{
    for (int i = 0; i <= n; ++i)
    {
        node[i].pre = i;
        node[i].rel = 0;
    }
    sum = 0;
}

int find(int x)
{
    if (x == node[x].pre)
        return x;
    int tmp = node[x].pre;
    node[x].pre = find(tmp);
    node[x].rel = (node[x].rel + node[tmp].rel) % 3; // 更新子节点与祖宗的关系
    return node[x].pre;
}

void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
    {
        node[fy].pre = fx; // 合并到fx
        node[fy].rel = (node[x].rel + d - 1 + 3 - node[y].rel) % 3; // 更新关系
    }
    else
    {
        if (d == 1 && node[x].rel != node[y].rel) // 同类且父辈相同要求与父辈关系相同
            sum++;
        else if (d == 2 && ((3 - node[x].rel + node[y].rel) % 3 != (d - 1))) // 不同类判断是否符合关系d-1
            sum++;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    init();
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n) // 超过n
        {
            sum++;
            continue;
        }
        if (d == 2 && x == y) // 同类自相残杀
        {
            sum++;
            continue;
        }
        merge(x, y); // 合并
    }
    printf("%d\n", sum);
    return 0;
}

交的时候用了while(scanf("%d%d", &n, &m) == 2) while (~scanf("%d%d", &n, &m))竟然WA了!!!找了一个小时的bug,我还能说什么!!!


The end.
2018-04-19 星期四
最后编辑于: 2018 年 05 月 06 日