[NOI2001] 食物链
阅读理解题石锤了。
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
每个动物都是 $A$，$B$，$C$ 的一种，意味着如果找到一条捕食链，就会多出一条头吃尾的信息。
又因为其中有着同类的复杂关系，简单的图关系可能很难描述。
那就用扩展域并查集。
我们尝试拆点，一个自然的思路就是把点拆成两份，一份（$x_{eat}$）代表 $x$ 今天吃什么，另一份（$x_{self}$）代表 $x$ 的同类是谁。
但是这样的话我们就不好找到那个链关系中头吃尾的信息了（就算找到了 $x$ 今天吃 $y$，而 $y$ 今天吃 $z$ 这种信息，普通的并查集会去查 $y_{eat}$ 的祖先，但得到的不一定是 $z_{self}$ 类型的点，也有可能是 $w_{eat}$ 这种，那么转化起来就麻烦了）。
当然你如果有高超的合并技巧可以尝试让 $z_{self}$ 类型的点当祖先，这样信息就准了。
那我们干脆拆成三个点，$x_{self}$，$x_{eat}$，$x_{enemy}$，分别表示 $x$ 的同类、捕食域、天敌域。
然后每次 $x$ 与 $y$ 同类的时候，我们将两者的三个域分别合并即可；若 $x$ 吃 $y$，则把 $x_{eat}$ 与 $y_{self}$、$x_{enemy}$ 与 $y_{eat}$、$x_{self}$ 与 $y_{enemy}$ 三个关系合并起来即可。
然后就是如何判断假话。
显然 $x$ 或 $y$ 大于 $n$ 要判，别忘了。
然后如果说 $x$ 与 $y$ 同类，则下面的条件与其矛盾（充要矛盾？）：
$x_{eat}$ 与 $y_{self}$ 在同一集合。
$x_{self}$ 与 $y_{eat}$ 在同一集合。
如果说 $x$ 吃 $y$，则下面的条件与其矛盾：
$x_{self}$ 与 $y_{self}$ 在同一集合。
$x_{self}$ 与 $y_{eat}$ 在同一集合。
然后就做完了。
当然用边带权并查集也是可以的。不过用到的就是其他技巧了。
代码（扩展域并查集）：
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=1e6;
ll n,m,ans;
ll fa[N+5];
inline ll Get(ll x) {if(x==fa[x]) return x;return fa[x]=Get(fa[x]);}
inline void Merge(ll x,ll y) {fa[Get(x)]=Get(y);}
int main() {
n=read();m=read();
for(ll i=1;i<=n*3;i++) fa[i]=i;
for(ll i=1;i<=m;i++) {
ll op,x,y;op=read();x=read();y=read();
if(x>n||y>n) {ans++;continue;}
if(op==1) {
if(Get(x+n)==Get(y)||Get(x)==Get(y+n)) ans++;
else {Merge(x,y);Merge(x+n,y+n);Merge(x+n+n,y+n+n);}
}
if(op==2) {
if(Get(x)==Get(y)||Get(y+n)==Get(x)) ans++;
else {Merge(x+n,y);Merge(x,y+n+n);Merge(x+n+n,y+n);}
}
}
write(ans);
return 0;
}
|