算法竞赛进阶指南：食物链

本文主要是介绍算法竞赛进阶指南：食物链，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接

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

输入格式

第一行是两个整数 N 和 K，以一个空格分隔。

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

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

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

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤50000,
0≤K≤100000

输入样例：

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

输出样例：

3

 思路：并查集维护根节点距离

我们先不考虑每两个动物x，y是什么关系，我们根据题目来判断；

如果x，y的取值在1~n，可以根据D的值判断是真话还是假话，或者判断将其变成真话；

假设x，y在一个集合 对于集合元素有h->a->b->c，h吃a，a吃b，b吃c，h到根节点距离为3，a到根节点距离为2，b到根节点距离为1；

可以推断出h和c是同类，他们之间的的距离为3%3=0，b被c吃，其到c的距离为2%3=2，a吃c，两者之间距离为1%3=1；

所以可以得出结论：如果x，y在一个集合 可以通过x和y到根节点的距离之差判断他们之间的关系，从而判断是真话还是假话；

如果距离之差%3=0，说明是同类，如果%3=1(x>y)，或者%3=-2(x<y)，说明x吃y；

如果不在同一集合，可以通过合并集合，调整其跟节点到新集合根节点的距离可以使其变成真话；

如果要是x，y不在同一集合，要使x，y为同类，则合并后(d[x]+d[p[x]]-d[y])%3=0，所以将其d[p[x]]变成d[y]-d[x]就行；

使x吃y也是同理：(d[p[x]]+d[x]-d[y]-1)%3=0，所以d[p[x]]=1+d[y]-d[x]；

d[p[x]]+d[x]-d[y]-1)%3=0与 x,y之差%3=1或者-2等价；

#include<iostream>
using namespace std;
const int N=5e5+10;
int p[N],d[N];//p数组存储x父节点，d存储x到根节点距离
int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);//需要先存储根节点，不将父节点更新为根节点
        //将父节点到根节点全部路径压缩指向根节点，同时更新父节点到根节点的距离
        d[x]+=d[p[x]];//点x到根节点距离=x到父节点距离+父节点到根节点距离
        p[x]=t;//更新父节点为根节点
    }
    return p[x];//返回根节点
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i) p[i]=i;
    int res=0;//假话个数
    while(k--){
        int D,x,y;
        cin>>D>>x>>y;
         if(x>n||y>n) {
             res++;//超出动物编号范围，为假
            continue;
         }
           int px=find(x),py=find(y);//x，y的父节点
         if(D==1){
            
           if(px==py&&(d[x]-d[y])%3!=0) res++;//判断是否为同一集合且同类
           
           else if(px!=py){//不为同一集合可变为同类
               p[px]=py;
               d[px]=d[y]-d[x];
           }

        }else{
            
             if(px==py&&((d[x]-d[y])%3!=1&&(d[x]-d[y])%3!=-2)) res++; 
             //x吃y的两种情况，距离之差%3=-1或者2
            
            else if(px!=py){
                p[px]=py;
                d[px]=1+d[y]-d[x];
            }
        }
    }
    cout<<res;
    return 0;
}

这篇关于算法竞赛进阶指南：食物链的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！