食物链（NOI2001,洛谷P2024）

题目描述

动物王国中有三类动物 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。

此人对 NN 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #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.

题目分析：

1.算法：N只动物，3个种类，直接能想到并查集；

   但食物链中又有3个种类之间的关系，

   因此，并查集中还应设有虚点，一种动物会有吃它们的动物与它们吃的动物，共3种，

    所以并查集的fa数组所开空间为3*n

(fa[1]~fa[n] ：fa[i]表示编号为i的动物所处集合的代表元，fa[n+1]~fa[2*n]表示吃编号为i-n的动物所处集合的代表元，fa[2*n+1]~fa[3*n]表示编号为i-2*n的动物所处集合的代表元）

并查集初始化：

for(int i=1;i<=3*n;i++) {f[i]=i;h[i]=0;}

基础的find与unio(n)操作：

int find(int k)
{if(f[k]==k) return k;else return f[k]=find(f[k]);
}

void unio(int x,int y)
{int xx=find(x);int yy=find(y);if(h[xx]==h[yy]) {h[xx]+=1;f[yy]=xx;}else{if(h[xx]>h[yy]) f[yy]=xx;else f[xx]=yy;}
}

主程序：

由题意可知

谎话有

1.x或y超出范围的：

int opt,x,y;
cin>>opt>>x>>y;
if(x>n||y>n||x<0||y<0) 
{ans++;continue;
}

2.操作1：

        x与y是同类但已知x吃y或y吃x;

        翻译：x与吃y的东西是同类或y与吃x的东西是同类；

        根据前文对f数组的定义可知，就是：

if(opt==1)
{if(find(x)==find(y+n)||find(y)==find(x+n)){ans++;continue;}
}

否则，把x与y及它们的天敌与它们的食物所在集合合并：

unio(x,y);
unio(x+n,y+n);
unio(x+2*n,y+2*n);

操作2：

x与y是同一样东西或它们是同一种动物或y吃x:

if(opt==2)
{if(x==y||find(x)==find(y)||find(y)==find(x+n)) {ans++;continue;}
}

否则由于它们的环状关系：

unio(x,y+n);
unio(x+n,y+2*n);
unio(y,x+2*n);

完整代码如下：

#include
using namespace std;
int n,m,f[1000001],h[1000001];
int find(int k)
{if(f[k]==k) return k;else return f[k]=find(f[k]);
}
void unio(int x,int y)
{int xx=find(x);int yy=find(y);if(h[xx]==h[yy]) {h[xx]+=1;f[yy]=xx;}else{if(h[xx]>h[yy]) f[yy]=xx;else f[xx]=yy;}
}
int main()
{cin>>n>>m;int ans=0;for(int i=1;i<=3*n;i++) {f[i]=i;h[i]=0;}for(int i=1;i<=m;i++){int opt,x,y;cin>>opt>>x>>y;if(x>n||y>n||x<0||y<0) {ans++;continue;}if(opt==1){if(find(x)==find(y+n)||find(y)==find(x+n)){ans++;continue;}unio(x,y);unio(x+n,y+n);unio(x+2*n,y+2*n);}if(opt==2){if(x==y||find(x)==find(y)||find(y)==find(x+n)) {ans++;continue;}unio(x,y+n);unio(x+n,y+2*n);unio(y,x+2*n);}}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！