python

7.4 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 240. 食物链

一、题目描述

动物王国中有三类动物 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，以一个空格分隔。

以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。

若 D=1，则表示 X 和 Y 是同类。

若 D=2，则表示 X 吃 Y。

输出格式 只有一个整数，表示假话的数目。

数据范围 1≤N≤50000,0≤K≤100000

输入样例：

输出样例：

本题目是一道非常好的并查集练习题，有两种并查集的解法，分别是扩展域并查集、带权并查集，下面分别进行介绍：

二、扩展域并查集

1、三点认知

两个同类元素的天敌集合是同一个集合，猎物集合也是同一个集合。
天敌的天敌是猎物 (因为是 食物环 嘛)
猎物的猎物是天敌 (因为是 食物环 嘛)

2、扩展域思想

1\sim n个元素扩大为1\sim 3n个元素，使用[1 \sim 3n]个并查集（每一个并查集中的所有元素都具有同一种特性，不同并查集中不存在相同元素）来维护3n元素彼此的关系。

为了形象化思考问题，我们假设三种动物，互为食物链：老鼠、大象、狐狸关系为:

狐狸杀死老鼠
大象拍死狐狸
老鼠钻鼻子大象

在这里x元素，x+n元素，x+2n元素三者的关系被定义为：

x元素的p[x]代表x家族
x+n元素的p[x+n]代表x的天敌家族
x+2n元素的p[x+2n]代表x的猎物家族

对于一句真话:

当x,y是同类
- 将他们的天敌集合（x+n与y+n所在集合）合并
- 将猎物集合（x+2n元素与y+2n元素所在集合）合并
- 将x,y所在的集合合并
当x是y的天敌
- ① 将x家族与y的天敌家族合并
- ② 将y家族和x的猎物家族合并
- ③ 将x的天敌家族和y的猎物家族合并

3、实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 150010;
int p[N];
int ans;
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void join(int x, int y) {
    int f1 = find(x), f2 = find(y);
    if (f1 != f2) p[f1] = f2;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= 3 * n; i++) p[i] = i; // 并查集初始化

    while (m--) {
        int x, y, t;
        cin >> t >> x >> y;
        // 说出大于n编号的动物，肯定是假话
        if (x > n || y > n) {
            ans++;
            continue;
        }
        if (t == 1) { // x和y同类
            if (find(x + n) == find(y) || find(x + 2 * n) == find(y)) {
                ans++;
                continue;
            }
            join(x, y);
            join(x + n, y + n);
            join(x + 2 * n, y + 2 * n);
        } else { // x吃y
                 // +n  天敌，+2n 食物
            if (find(x) == find(y) || find(x + n) == find(y)) {
                ans++;
                continue;
            }
            join(x, y + n);
            join(x + n, y + 2 * n);
            join(x + 2 * n, y);
        }
    }
    printf("%d\n", ans);
    return 0;
}

二、带权并查集

功能：查询祖先+修改父节点为祖先+更新节点到根的距离（通过到父节点的距离累加和） d[i]的含义：第 i 个节点到其父节点距离。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;
const int M = 3;

/**
 带权并查集：
 (1)不管是同类，还是吃与被吃的关系，都把它们放到同一个链中去
 (2)还没有关联关系的两条链,是两条彼此独立的链
 (3)同一个链中动物关系用距离根结点的长度来描述: 0:同类，1：吃, 2:被吃
 通过上面的记录关系，就可以推理出任何两个节点的关系
 */

int n, m;
int p[N]; // 家族
int d[N]; // i结点到父结点的距离
int res;  // 假话的个数

// 带权并查集find模板
// ① 需要将原始并查集的find模板一拆为二
// ② 在拆分的两句话中间，增加更新到父节点距离的代码
int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] = (d[p[x]] + d[x]) % M; // 父亲到根据的距离+自己到父亲的距离=自己到根的距离
        p[x] = t;
    }
    return p[x];
}

int main() {
    cin >> n >> m;
    // 并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;

    // m个条件
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;
        // 如果出现x,y的序号，大于最大号，那么肯定是有问题，是假话
        if (x > n || y > n) {
            res++;
            continue;
        }
        // 祖先
        int px = find(x), py = find(y);

        if (t == 1) {                          // x,y同类
            if (px != py) {                    // 没有处理过 x,y的关系
                p[px] = py;                    // 记录x,y的关系，把两个链合并一下，px认py为家族族长
                d[px] = (d[y] - d[x] + M) % M; // x,y是同类，则d[px] + d[x]= 0 + d[y]
            } else if ((d[x] - d[y] + M) % M)  // 在同一个家族中，x,y同类,则d[x]=d[y],即d[x]-d[y]=0,不等于0，假话
                res++;
        }

        if (t == 2) {                              // x吃y
            if (px != py) {                        // 没有处理过x,y的关系
                p[px] = py;                        // 记录x,y的关系，把两个链合并一下，px认py为家族族长
                d[px] = (d[y] + 1 - d[x] + M) % M; // x吃y,则d[px]+d[x]-1=d[y]
            } else if ((d[x] - d[y] - 1 + M) % M)  // 在同一个家族中，x吃y,则d[x]-d[y]=1,即d[x]-d[y]-1=0，要是不等于0，假话
                res++;
        }
    }
    // 输出
    printf("%d\n", res);
    return 0;
}

代码解释：

7.4 KiB Raw Permalink Blame History Unescape Escape