食物链 poj-1182

题面:

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

 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

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

 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

Sample Output

3

 
  • 1

这道题明显是一道使用并查集算法的题目,因为牵涉到两个动物是否同为一类的问题。因为所有动物都属于A,B,C中的其中一种。所以在的到n种动物的数据后,初始化为3 * n个节点。这样做的目的主要是用来表示捕食关系。
若给的两个动物属于同一类,则执行将每一个n范围的节点中代表的两个动物放在一个集合中。
用计算机语言来表达就是:

if(a == 1) {    //x和y属于同一类的信息
    if(same(b, c + m) || same(b, c + 2*m)) {    //判断b和c在之前的情况中,是否已构成捕食与被捕食的关系
        ans++;
    } else {    //如果没有捕食关系,则在3个区间中把b和c放在一起
        unite(b, c);
        unite(b + m, c + m);
        unite(b + m*2, c + m*2);
    }
}

 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

若给的两个动物是捕食关系,则执行将第一个n范围中的第一个动物捕食第二个n范围中的第二个动物,第二个n范围汇总的第一个动物捕食第三个n范围中的第二个动物,第三个n范围中的第一个动物捕食第一个范围中的第二个动物。
用计算机语言表达就是:

if(t == 2) {    //x吃y的信息
    if(same(b, c) || same(b, c + 2*m)) {    //判断b和c是否为同一类或者已经构成c吃b的捕食关系,若是则为错ans+1
        ans++;
    } else {
        unite(b, c + m);
        unite(b + m, c + 2*m);
        unite(b + 2*m, c);
    }
}

 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int SIZE = 1e6+5;
int n, k;
int par[SIZE], Rank[SIZE];
void init(int x) {
    for(int i = 0; i < x; i++) {
        par[i] = i;
        Rank[i] = 0;
    }
}
int Find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = Find(par[x]);
    }
}
void unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    if(x == y)
        return;
    if(Rank[x] < Rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if(Rank[x] == Rank[y])
            Rank[x]++;
    }
}
bool same(int x, int y) {
    return Find(x) == Find(y);
}
int main() {
    int m, n, a, b, c, ans;
    scanf("%d%d", &m, &n);
    init(m*3);  //初始化:准备m*3个节点表示n个元素
    ans = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        b--, c--;
        if(b < 0 || b >= m || c < 0 || c >= m) {    //判断b和c是否在范围里面
            ans++;
            continue;
        }
        if(a == 1) {    //x和y属于同一类的信息
            if(same(b, c + m) || same(b, c + 2*m)) {    //判断b和c在之前的情况中,是否已构成捕食与被捕食的关系
                ans++;
            } else {    //如果没有捕食关系,则在3个区间中把b和c放在一起
                unite(b, c);
                unite(b + m, c + m);
                unite(b + m*2, c + m*2);
            }
        } else {    //x吃y的信息
            if(same(b, c) || same(b, c + 2*m)) {    //判断b和c是否为同一类或者已经构成c吃b的捕食关系,若是则为错ans+1
                ans++;
            } else {
                unite(b, c + m);
                unite(b + m, c + 2*m);
                unite(b + 2*m, c);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71

参考:挑战程序设计竞赛