NOI2001食物链 题解

题目链接

又是一道食物链……

最近怎么和食物链有缘似得qwq

还是很水的一道题。

对于任意两个动物A、B是同类,那么存在:

  • A的同类和B的同类
  • A的猎物是B的猎物
  • A的天敌是B的天敌

同理,对于任意两个动物存在A捕食B的关系:

  • A的同类是B的天敌
  • A的猎物是B的同类
  • A的天敌是B的猎物

开个并查集,分三段。一段同类,一段猎物,一段天敌。

维护一下上述关系就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>

class UnionFind
{
private:
int *father;

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

public:
UnionFind(int n)
{
father=new int[n+1];
for(int i=1;i<=n;i++)
father[i]=i;
}

~UnionFind()
{
delete [] father;
}

bool SameSet(int x,int y)
{
return find(x)==find(y);
}

void Union(int x,int y)
{
father[find(x)]=find(y);
}

};

int n,k,ans;

#define self(x) x //同类
#define pery(x) x+n //猎物
#define enemy(x) x+n+n //天敌

int main()
{
scanf("%d%d",&n,&k);
static UnionFind *animal=new UnionFind(n*3);
for(int i=1;i<=k;i++)
{
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(x>n||y>n)
{
ans++;
continue;
}
if(opt==1)
{
if(animal->SameSet(pery(x),self(y)) //如果A是B的天敌,谎言
|| animal->SameSet(enemy(x),self(y))) //如果A是B的猎物,谎言
{
ans++;
continue;
}
animal->Union(self(x),self(y)); //A的同类和B的同类
animal->Union(pery(x),pery(y)); //A的猎物是B的猎物
animal->Union(enemy(x),enemy(y)); //A的天敌是B的天敌
}
else if(opt==2)
{
if(animal->SameSet(self(x),self(y)) //如果A是B的同类,谎言
|| animal->SameSet(enemy(x),self(y))) //如果A是B的猎物,谎言
{
ans++;
continue;
}
animal->Union(self(x),enemy(y)); //A的同类是B的天敌
animal->Union(pery(x),self(y)); //A的猎物是B的同类
animal->Union(enemy(x),pery(y)); //A的天敌是B的猎物
}
}
printf("%d\n",ans);
delete animal;
return 0;
}