240. 食物链

2021年09月15日 阅读数:5
这篇文章主要向大家介绍240. 食物链,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目传送门c++

1、扩展域并查集

详解将\(1\sim n\)个元素扩大为\(1\sim 3n\)个元素的缘由以及意义:数组

首先本题的解法是将\(1\sim n\)个元素扩大为\(1\sim 3n\)个元素,使用\([1,3n]\)个并查集(每个并查集中的全部元素都具备同一种特性,不一样并查集中不存在相同元素)来维护\(3n\)元素彼此的关系。框架

在这里咱们留下两个问题:1.为何是\([1,3n]\)个并查集?2.为何要有\(3n\)个元素?
它们在后续会获得解答
在这里\(x\)元素,\(x+n\)元素,\(x+2n\)元素三者的关系被定义为:
\(x\)元素所在集合中全部\(∈[1,n]\)的元素都是\(x\)元素的同类
\(x+n\)元素所在集合中全部\(∈[1,n]\)的元素都是\(x\)元素的天敌
\(x+2n\)元素所在集合中全部\(∈[1,n]\)的元素都是\(x\)元素的猎物
\(x+n\)元素所在的集合中全部\(∈[1,n]\)的元素都是\(x+2n\)元素的猎物学习

这里又多出了一个问题:为何要这样定义?
相信不少人看到这里的时候依旧是懵逼的,但不要紧,先回过头去再看一遍上面的文字,理清本身脑中有哪些疑问,再接着往下看
当咱们获得一句关于两个元素\(x,y\)彼此关系的描述时,咱们若是已知目前\(x,y\)它们各自的猎物和天敌,以及它们是不是同类,就能够判断这句描述的真假
这时咱们来分析一下上面定义的做用
咱们能够经过\(x+n\)元素来肯定\(x\)元素目前已知的天敌,也能够经过\(x+2n\)元素来肯定\(x\)元素目前的猎物,还能够经过\(x\)元素自己来肯定\(x\)的同类spa

因而借此咱们就可以进行语言真假的判断了
那么要怎样操做才能使全部的元素知足定义呢?
咱们只须要认清如下几点:
1.两个同类元素的天敌集合是同一个集合,猎物集合也是同一个集合
2.天敌的天敌是猎物
3.猎物的猎物是天敌code

对于一句真话,当\(x\)元素,\(y\)元素是同类时,将他们二者的天敌集合(\(x+n\)元素与\(y+n\)元素所在集合)和猎物集合(\(x+2n\)元素与\(y+2n\)元素所在集合)以及自身所在的集合分别合并。当\(x\)元素是\(y\)元素的天敌时,将\(x\)元素所在集合与\(y\)元素的天敌集合合并,将\(y\)元素所在集合和\(x\)元素的猎物集合合并,将\(x\)元素的天敌集合和\(y\)元素的猎物集合合并cdn

如今来回答先前的问题:
1.为何是\([1,3n]\)个并查集?
由于不断合并后的并查集数量只有这么多。blog

2.为何有\(3n\)个元素?
由于要知足上述的定义。递归

3.为何要这样定义?
由于这样定义能够完美的解决问题,它被称为规则ip

最后再发表在下的一点见解:
“为何要这样作?”是咱们在学习中最常遇到的问题,但有时候这个问题真的很恐怖。就如同咱们知道\(1+1=2\),可是当你产生“”为何\(1+1=2\)”这样一个问题时就会感到恐惧,由于你发现你是在质疑规则,但规则是不能被撼动的,不然一切都会消失,因此你的问题将永远没法获得解答,因而乎你就会掉入思惟的无底洞。
学习的过程是打破砂锅问到底,但你最好祈祷你本身不会打破砂锅,由于根本没有底。

#include<bits/stdc++.h>

using namespace std;
const int N = 150010;
int fa[N];
int ans;
//带扩展域的并查集
/**
 * 功能:寻找祖先
 * @param x
 * @return
 */
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

//加入家族集合中
void join(int x, int y) {
    int f1 = find(x), f2 = find(y);
    if (f1 != f2)fa[f1] = f2;
}

int main() {
    int n, m;
    cin >> n >> m;
    //开三个并查集,合用一个数组表示
    //对于每种生物:设x为自己,x+n为猎物,x+2*n为天敌
    for (int i = 1; i <= 3 * n; i++) fa[i] = i; //初始化

    while (m--) {
        int x, y, t;
        cin >> t >> x >> y;
        // 太大了,越界了,确定是假话
        if (x > n || y > n) {
            ans++;
            continue;
        }
        //xy同类
        if (t == 1) {
            //若是y是x的天敌或猎物,为谎话
            if (find(x + n) == find(y) || find(x + 2 * n) == find(y)) {
                ans++;
                continue;
            }
            //x的同类和y的同类,x的猎物是y的猎物,x的天敌是y的天敌
            join(x, y);
            join(x + n, y + n);
            join(x + 2 * n, y + 2 * n);
        }
        //y是x的猎物
        if (t == 2) {
            //若是x是y的同类或猎物,为谎话
            if (find(x) == find(y) || find(x + 2 * n) == find(y)) {
                ans++;
                continue;
            }
            join(x, y + 2 * n);//x的同类是y的天敌
            join(x + n, y);//x的猎物是y的同类
            join(x + 2 * n, y + n); //x的天敌是y的猎物
        }
    }
    printf("%d\n", ans);
    return 0;
}

2、带权并查集

功能:查询祖先+修改父节点为祖先+更新节点到根的距离(经过到父节点的距离累加和)
\(d[i]\)的含义:第 \(i\) 个节点到其父节点距离。

const int M=3;

int find(int x){
    if(p[x] != x){
        int t = find(p[x]);
        d[x] = (d[x]+d[p[x]])%M; //为啥要模M?由于一共3个数,0,1,2,若是2+2,咱们保存1就能够
        p[x] = t;
    }
    return p[x];
}

对比一下裸的并查集查询祖先+修改父节点为祖先的代码

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]); 
    return p[x];
}

注意事项:即明白 \(d[i]\) 的含义
https://cdn.acwing.com/media/article/image/2021/01/08/2675_ab3bf90451-3.jpg

(1)找到祖先

(2)将祖先设置为父节点(路径压缩)

参考: https://www.acwing.com/solution/content/33576/

(3)更新d[i]

这个更新d[i]是此题的精髓,由于通常考并查集,应该不会考裸的,没有区分度,确定要加一些附加信息才对。那么加什么样的附加信息呢?前一题加的是最基本的家族成员个数,比较简单,这个有难度,须要将场景向并查集模型靠拢,同时对于节点到父节点的距离加以利用,这应该是并查集的一种常见扩展形式。

由于原来的d[i]描述的是节点i与父节点的距离,如今父节点变成了祖先节点,这个距离确定不对了,须要更新。

那么如何进行更新呢?这就须要咱们对于上面的递归过程进行仔细体会,理解清楚在递归过程当中都发生了什么,是怎么发生的。其实在裸的递归过程当中,发生了3件事:
(1)向父节点询问祖先。
(2)父节点递归查找祖先
(3)每一个涉及到的节点更新本身的父节点为祖先节点。(每一个是指一路走来的全部儿子->父亲->爷爷->太爷爷---...-->老祖宗(老祖宗其实没有更新本身的父节点,由于没有必要更新))

离老祖宗最近的那个老太爷,他的d[i]是纯的d[i],而这个老太爷的儿子节点,d[ii]实际上是d[ii]=d[ii]+d[i]了,是一路叠加的 d[x]+=d[p[x]],就是累加的路径长度。

这一块的

int t = find(p[x]);             //t是祖先
d[x] = (d[x]+ d[p[x]])%M;       //压缩了节点到根的距离
p[x] = t;

为何要使用变量记录下来?
这是由于: 裸的并查集框架

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]); 
    return p[x];
}

第一步操做,实际上是作了两件事,一件事是递归找祖先,另外一件事是顺带把一路上的节点的父亲修改成祖先。
若是沿袭这样的逻辑,就势必将每一个节点到父节点的距离丢失了,由于还没等处理,父节点就修改完了,换句话说,要把两步分开,找祖先是找祖先,修改父节点是修改父节点,两步拆开后,中间能够在父节点尚未修改前,使用这个父节点,找到父节点到爷爷结点的d[i]距离!

C++ 代码

#include <bits/stdc++.h>

using namespace std;

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

/**
 * 并查集:
 * 维护额外信息,本题维护的是每一个节点到父节点的距离
 * 并查集中每一个集合是树的形式
 * 不论是同类,仍是吃的关系,咱们都把它们放到同一个集合中去。它们之间的关系用距离描述。
 * 经过上面的记录关系,咱们就能够推理出任何两个节点的关系。
 */
int n, m;
int p[N]; //父亲是谁
int d[N]; //i结点到父结点的距离
int res;  //假话的个数

/**
 * p是指节点i的父节点是谁
 * d是指节点i到本身父亲的距离
 * d[x]=1 : x吃根结点
 * d[x]=2 : x被根结点吃
 * d[x]=0 : x与根结点是同类
 * @param x
 * @return
 */
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);
        //t==1,同类
        if (t == 1) {
            //同一个家族,并且距离值差模3不等于0,表示不是同类,结果值++
            if (px == py && (d[x] - d[y] + M) % M) res++;
            //若是不是同一个家族,须要合并并查集
            if (px != py) {
                p[px] = py;//将px认py为祖先
                d[px] = (d[y] - d[x] + M) % M;  //修改路径长度
            }
        }
        //t==2,表示X吃Y
        if (t == 2) {
            //同一个家族,但距离并非1,那就是错误答案
            if (px == py && (d[x] - d[y] + M) % M != 1) res++;
            //不在同一个家族内
            if (px != py) {
                p[px] = py;//将px认py为祖先
                d[px] = (d[y] + 1 - d[x] + M) % M;//修改路径长度
            }
        }
    }
    //输出大吉
    printf("%d\n", res);
    return 0;
}