洛谷 P2024 [NOI2001] 食物链

[NOI2001] 食物链

传送门

题目描述

动物王国中有三类动物 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 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

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

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

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

样例输出 #1

3

提示

1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5

带权并查集

pre[i]：记录 i 的祖宗结点
dis[i]：i 和 它祖宗的关系
0 代表和上面是同类，1 代表捕食上面的，2 代表被上面的捕食
但是如果路径压缩之后，dis代表的关系就失效了，所以我们要更新关系，dis[x] = (dis[pre[x]] + dis[x]) % 3;，这样仍然可以代表跟父亲结点的关系。== +3 之后再%，只是因为怕有负数==
路径压缩之后，除了祖宗结点之外，每个点都直接指向自己所在集合的祖宗结点，并且和祖宗结点有固定的关系
我们根据向量来计算
如果原来没有关系，并不是同一个集合，要合并，就要求出来两个祖宗结点的关系

如果是同一个集合的，连接的是同一个根节点，要求出两个结点直接的关系

/** * @author Changersh * @date 2022/7/23 11:22 * 0 同类，1 捕食上面的，2 被上面的捕食 */

import java.util.*;
import java.lang.*;
@SuppressWarnings({
    "all"})
public class Main {
    
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        // 初始化
        for (int i = 1; i <= n; i++) pre[i] = i;
        Arrays.fill(dis, 0);

        int cnt = 0;
        while (k-- > 0) {
    
            int opt = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            if (x > n || y > n) {
     // 不是这 n 种动物
                cnt++;
                continue;
            }
            int fx = find(x), fy = find(y);
            if (opt == 1) {
     // x y 是同类
                if (fx == fy && dis[x] != dis[y]) {
     // 两个人在同一个集合，但是跟根节点关系不一样，不同同类
                    cnt++; // 假话
                    continue;
                }
                else {
     // 不在同一个集合，说明之前不存在关系，合并两个人即可
                    pre[fx] = fy;
                    dis[fx] = (0 + dis[y] - dis[x] + 3) % 3; // 按照xy同类关系，计算出根节点的关系
                }
            }
            else {
      // x 吃 y
                if (fx == fy && (dis[x] - dis[y] + 3) % 3 != 1) {
    
                    // 属于同一个集合，但是不是捕食关系，是假话
                    cnt++;
                    continue;
                }
                else {
     // 如果不在同一个集合里，是真话，合并
                    pre[fx] = fy;
                    dis[fx] = (dis[y] + 1 - dis[x] + 3) % 3;
                }
            }
        }
        System.out.println(cnt);
    }
    private static int[] pre = new int[50005];
    private static int[] dis = new int[50005];
    private static int find(int x) {
    
        if (pre[x] != x) {
    
            int u = find(pre[x]);
            dis[x] = (dis[pre[x]] + dis[x]) % 3;
            pre[x] = u;
        }
        return pre[x];
    }
}

种类并查集

开三倍大小，1 - n是同类，n+1 - 2n是猎物，2n+1 - 3n 是天敌
之后就是分情况讨论了，看代码吧

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include<unordered_map>
#include <unordered_set>

using namespace std;

// 种类并查集写法
const int maxN = 5e4 + 5;
int pre[maxN * 3], n, k, ans; // 三倍的pre大小，1 是同类，2 是猎物，3 是天敌

int find(int x) {
     return pre[x] == x ? pre[x] : find(pre[x]); }

int main() {
    
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n * 3; i++) pre[i] = i; // 初始化
	
	for (int i = 1; i <= k; i++) {
    
		int opt, x, y;
		scanf("%d %d %d", &opt, &x, &y);
		if (x > n || y > n) {
     // 不是这 n 种动物
			ans++;
			continue;
		}
		
		if (opt == 1) {
     // 第一种情况，x y 是同类
			if ((find(x + n) == find(y)) || (find(x + 2 * n) == find(y))) {
     // y是 x 的猎物或者同类，说明是假话
				ans++;
			} else {
    
				pre[find(x)] = find(y);                 // x y 是同类
				pre[find(x + n)] = find(y + n);         // x 的猎物 是 y 的猎物
				pre[find(x + 2 * n)] = find(y + 2 * n); // x 的天敌 是 y 的天敌
			}
		} else {
     // 第二种情况，x 吃 y
			if ((find(x) == find(y)) || (find(x + 2 * n) == find(y))) {
     // x y 是同类，或者 y 是 x 的天敌，是假话
				ans++;
			} else {
    
				pre[find(x + n)] = find(y);         // x 的猎物 是 y 的同类
				pre[find(x + 2 * n)] = find(y + n); // x 的天敌 是 y 的猎物
				pre[find(x)] = find(y + 2 * n);     // x 的同类 是 y 的天敌
			}
		}
	}
	
	printf("%d\n", ans);
	return 0;
}