寒假私训 ——并查集 B - 食物链

题目大意

动物王国中有三类动物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(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

Input
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
Output
只有一个整数,表示假话的数目。
Sample Input

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

Sample Output

3

解题思路

这一题容易想简单咯,我刚开始错误的理解成前面我做过的一道题——团伙,所以我以为这个食物链问题就是简简单单的两个树——朋友树和敌人树,所以刚开始我的代码这样写的:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e3+7;
int f[maxn],a[maxn];  //上级数组,i当前的父亲节点
int n,k,d,x,y,num;
int findf(int x){    //查找朋友上级
    return f[x]==x?x:f[x]=findf(f[x]);
}
int finda(int x){    //查找敌人上级
    return a[x]==x?x:a[x]=finda(a[x]);
}
void add(int d,int x,int y){  //合并操作

    if(d==1)
               f[x]=y;
    else if(d==2)
               a[x]=y;
}

void Init(int n){   //初始化
    for(int i=1;i<=n;i++){f[i]=i;a[i]=i;}
}
int main(){
    cin>>n>>k;
    Init(n);
    num=0;
    while(k--){
               cin>>d>>x>>y;
    if(x>n||y>n){
                            num+=1;
                            cout<<"-"<<endl;
                            continue;
               }
    else if(x==y&&d==2){
                              num+=1;
                              cout<<"--"<<endl;
                              continue;
               }
    int x1=findf(x);
          int y1=findf(y);
               int x2=finda(x);
               int y2=finda(x);
               if((d==1)&&x1!=y1&&x2==y2){
                              num+=1;
                              cout<<"---"<<endl;
                              continue;
               }
               else  if((d==2)&&x2!=y2&&x1==y1){
                              num+=1;
                              cout<<"----"<<endl;
                              continue;
               }
    if(x1!=y1&&x2!=y2){
               add(d,x,y);
               }
    }
    cout<<num<<endl;
    return 0;
}

答案错了,我发现,不能把他看成简单的并查集,应该另外找个思路,重新分析每个节点与节点之间的关系。
什么是带权并查集?
答:在对并查集进行路径压缩和合并操作时,这些权值具有一定属性,即可将他们与父节点的关系,变化为与所在树的根结点关系。

应该记录下每一个根节点和他的子节点的关系,假设:
a->b偏移量0时a和b同类
a->b偏移量1时a被b吃
a->b偏移量2时a吃b
建立一个结构体。但是多加入的关系会让节点之间的关系搜索变得复杂,这里通过向量的知识分析一下d=1和2情况下,a的根节点和b的根节点的关系:

  1. 如果a的根节点等于b的根节点:说明a和b在一棵树上,要确定a和b的关系,就要知道a->根节点的关系和根节点->b的关系(这里的方向问题不要搞混!!)
    即,(x->y).relation=(x->rx).relation+(rx->y).relition
    =(3-relation[x]+relation[y])%3
  2. 如果a的根节点不等于b的根节点:说明a和b在不同的树上,要确定a和b的关系,就要知道a->a的根节点的关系和a的根节点->b的根节点和b的根节点->b的关系。
    即,rx->ry=(relation[x]+d-1+3-relation[y])%3=relation[ry]

另外,这一题输入输出只能scanf和printf,否则会超时!!!

具体代码如下:

代码

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 50010
typedef long long ll;
struct node{
     int num;
     int relation;
}f[maxn];
int n,k,d,x,y,sum;
int find(int x){
    int temp;
    if(x==f[x].num) return x;
    temp=f[x].num; //路径压缩
    f[x].num=find(temp);
    f[x].relation=(f[x].relation+f[temp].relation)%3; //关系域更新
    return f[x].num; //根结点
}
void add(int x,int y,int d){
    int f1=find(x);
    int f2=find(y);
    f[f2].num=f1; //合并树 注意:被 x 吃,所以以 x 的根为父
    f[f2].relation=(f[x].relation-f[y].relation+3+(d-1))%3; //对应更新与父节点的关系
}

void Init(int n){   //初始化
    for(int i=1;i<=n;i++){f[i].num=i;f[i].relation=0;}
}
int main(){
    scanf("%d%d",&n,&k);
    Init(n);
    sum=0;
    while(k--){
                   scanf("%d%d%d",&d,&x,&y);
    if(x>n||y>n||(x==y&&d==2)){
                            sum+=1;
                            //cout<<"-"<<endl;
                            continue;
               }
    else if(find(x)==find(y)){
    if((d==1)&&f[x].relation!=f[y].relation){  //如果x与y是同类,则说明两者根节点的关系是一样的
                              sum+=1;
                              //cout<<"---"<<endl;
                              continue;
               }
    else  if((d==2)&&(3-f[x].relation+f[y].relation)%3!=d-1){//此时要满足x吃y,则必须满足x的根节点吃y,即f[y].relation=1,
                              sum+=1;
                              //cout<<"----"<<endl;
                              continue;
               }
    }
    else
               add(x,y,d);
    }
    printf("%d\n",sum);
    return 0;
}

寒假私训 ——并查集 B - 食物链寒假私训 ——并查集 B - 食物链 atnana 发布了26 篇原创文章 · 获赞 0 · 访问量 575 私信 关注
上一篇:2019 ACL 论文阅读:Learning Attention-based Embeddings for Relation Prediction in Knowledge Graphs


下一篇:php-如何在Laravel中使用hasMany关系和hasMany获取数据?