[题目链接] – [NOI2001] 食物链

[NOI2001] 食物链

题目描述

动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。ABBCCA。 现有 N 个动物,以 1 \sim N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述: – 第一种说法是 1 X Y,表示 XY 是同类。

  • 第二种说法是2 X Y,表示 XY

此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。 – 当前的话与前面的某些真的话冲突,就是假话;

  • 当前的话中 XYN 大,就是假话;
  • 当前的话表示 XX,就是假话。

你的任务是根据给定的 NK 句话,输出假话的总数。

输入格式

第一行两个整数,N,K,表示有 N 个动物,K 句话。 第二行开始每行一句话(按照题目要求,见样例)

输出格式

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

样例 #1
样例输入 #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\le N\le 5 \times 10^41\le K \le 10^5。 #### 题目分析

这个题可以用并查集做。 一开始想到用三个标记分别标记三种动物的共同祖先,这样每次check一下祖先就可以找到关系。但是这样情况有点多,题目不太好做。 可以开三倍的并查集,下标分别从1n+1n2+1开始,分别为ABC类,注意这里ABC只表示相互关系,而不是确切的种类。我们认为A类会去吃B类,以此类推。每类中,已知的同伴都是在一个并查集里,同时,A类的布施者会与B中的被捕者联系。当check同类中的两者,观测到的是同伴关系,当check$相邻两分类的两者,观测到的是捕食关系。 这种并查集被称为 种类并查集,可以帮助你更加深刻地理解并查集。

代码

#include<bits>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x)  (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 5e4 + 10;
int fa[N * 3];
int n, k;
int find(int pos) {
  if(fa[pos] != pos) fa[pos] = find(fa[pos]);
  return fa[pos];
}
inline void merge(int posx, int posy) {
  int rtx = find(posx);
  int rty = find(posy);
  if(rtx != rty) fa[rtx] = rty;
}
inline bool check(int posx, int posy) {
  int rtx = find(posx);
  int rty = find(posy);
  return rtx == rty;
} 
/*A吃B,B吃C,C吃A*/
int main()
{
  // freopen(P2024_2.in, r, stdin);
  // freopen(P2024.out, w, stdout);
  scanf(%d%d, &n, &k);
  for(int i = 1; i  n || y > n) {fake++; continue;}
    if(jud == 1) {//同类
      if(check(x, y + n) || check(x, y + n * 2)) fake++;
      else {merge(x, y); merge(x + n, y + n); merge(x + n * 2, y + n * 2);}
    }
    if(jud == 2) {//吃
      if(x == y) fake++;
      else if(check(x, y) || check(x, y + n * 2)) fake++;
      else {merge(x, y + n); merge(x + n, y + n * 2); merge(x + n * 2, y);}

    }
  }
  printf(%d\n, fake);
  return 0;
}
</bits>