P2024 [NOI2001]食物链

男娘i 2023-03-04 14:28 16阅读 0赞

# P2024 \[NOI2001\]食物链 #

![博客图片][format_png]

## 题目链接 ##

[P2024 \[NOI2001\]食物链][P2024 _NOI2001]

[POJ1182][]

## 题目概述 ##

存在三类动物 A , B , C A,B,C A,B,C,他们之间构成 A A A吃 B B B, B B B吃 C C C, C C C吃 A A A的循环食物链关系,现在给出一组输入,总共有 N N N中动物, K K K行输入表示这些动物之间的食物关系:

1.  `1 X Y`,表示 X X X和 Y Y Y是同类动物;
2.  `2 X Y`,表示 X X X吃 Y Y Y.

读取这 K K K行语句,只要其中一行语句满足下面三个条件之一,这个语句就是假的,否则为真:

1.  当前的话与前面的某些真的话冲突,就是假话
2.  当前的话中 X X X或 Y Y Y比 N N N大,就是假话
3.  当前的话表示 X X X吃 X X X,就是假话  
    输出这 K K K个语句中假话的个数,输入数据规模:  
     1 ≤ N ≤ 5 ⋅ 1 0 4 , 1 ≤ K ≤ 1 0 5 1 \\leq N \\leq 5\\cdot 10^4, 1 \\leq K \\leq 10^5 1≤N≤5⋅104,1≤K≤105

## 思路分析 ##

很明显,如果单独处理同一类动物,用一个简单的并查集就可以处理了,但是题目中还限制了一种捕食关系,对于任意一种动物,这个并查集应该能够维护关于结点 X X X的下面三种关系:

1.  X的等价动物集合的代表元素
2.  X可以捕食的动物的集合的代表元素
3.  X被捕食的动物的集合的代表元素

我最初是使用了三个并查集,尝试维护这个关系,但是这样的一个关系有一个没法解决的问题,就是这个三个并查集初始时每个位置代表的集合的元素无法完全不同,比如说第一个里面并查集里面 X X X表示与动物 X X X是同一类动物的代表,但是到了第二个里面又变成了动物 X X X可以捕食的代表,这样最终通过查询根节点找到的那个没法有效清晰的表示这个是那种关系的其中一种.一种解决方案以给定动物的种类数量 N N N作为偏移量,表示这种动物可以捕食或者被捕食的动物的集合的代表元素.

对于输入的一行约束条件为假,存在以下这样的情况:

1.   X > N , o r , Y > N X > N ,or,Y > N X>N,or,Y>N
2.   X X X与 Y Y Y是同一类,但是此前得到 X X X与 Y Y Y之间存在捕食关系,可能是 X X X捕食 Y Y Y也可以是 Y Y Y捕食 X X X.
3.   X X X与 Y Y Y存在捕食关系,但是此前的条件可以推出 X X X与 Y Y Y是同一类,或者是 Y Y Y可以捕食 X X X.  
    如果不满足上面的情况,显然这个约束项应该被加入到里面,根据 X X X和 Y Y Y之间的关系不同,更新原来集合关系的操作也不同:
4.  如果 X X X与 Y Y Y是同一类,那么要更新 X X X本身和 Y Y Y处于同一个集合,也就是合并两个集合;更新 X X X捕食者的集合和 Y Y Y捕食者的集合为同一个集合;更新捕食 X X X和捕食 Y Y Y的动物的集合为同一个集合.
5.  如果 X X X与 Y Y Y之间是捕食关系,那么更新 X X X的捕食者为 Y Y Y表示 X X X捕食 Y Y Y,同时更新捕食 X X X的集合为 Y Y Y捕食的动物以及更新集合 X X X为捕食 Y Y Y的集合

## 代码实现 ##

/*
     * @Author: Shuo Yang
     * @Date: 2020-08-03 19:39:26
     * @LastEditors: Shuo Yang
     * @LastEditTime: 2020-08-03 19:43:02
     * @FilePath: /Code/POJ/1182.cpp
     */
    #include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    const int N = 1e6+5;
    int s[N];
    
    
    int find_set(int x){
        
        if( s[x] == x)
            return x;
        int r = x;
        while( s[r] != r){
        
            r = s[r];
        }
        while( x != r){
        
            int t = s[x];
            s[x] = r;
            x = t;
        }
        return r;
    }
    
    int main(int argc, const char** argv) {
        
        for(int i = 0; i < N; ++i)
            s[i] = i;
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n,k;
        cin>>n>>k;
        int ans = 0;
        for(int i = 0; i < k; ++i ){
        
            int c,x,y;
            cin>>c>>x>>y;
            // scanf("%d %d %d", &c,&x,&y);
            if(x > n || y > n){
        
                ++ans;
                continue;
            }
            if( c == 1){
        
                if(find_set(x + n) == find_set(y) ||find_set( x ) == find_set(y+n)){
        
                    ++ans;
                }else{
        
                    s[find_set(x)] = find_set(y);
                    s[find_set(x+n)] = find_set(y+n);
                    s[find_set(x+2*n)] = find_set(y+2*n);
                }
            }else{
        
                if( find_set(x) == find_set(y) || find_set(x+2*n) == find_set(y)){
        
                    ++ans;
                }else{
        
                    s[find_set(x+n)] = find_set(y);
                    s[find_set(x+2*n)] = find_set(y + n);
                    s[find_set(x)] = find_set(y+2*n);
                }
            }
        }
        cout<<ans<<endl;
        return 0;
    }

在POJ上这道题如果用上面的代码提交会`TLE`,但是当把输入换做`scanf`时确可以`AC`;换到洛谷上速度会比之前的取消同步的`cin`快一点.

## 其它 ##

[format_png]: /images/20230208/b940341665b541bd806a7217b28e6f9e.png
[P2024 _NOI2001]: https://www.luogu.com.cn/problem/P2024
[POJ1182]: http://poj.org/problem?id=1182