问题描述
问题分析
也是因为OJ问题卡主了几天的一个题
复制一下当时写的时候写的一些想法
不矛盾的情况下
x,y同类 则 xA-yA xB-yB xC-yC 可以合并
x吃y 则 xA-yB xB-yC xC-yA 可以合并
并查集 体现在
把关系可以成立的合并
那么通过查询两元素是否为同一集合
则可推断这一关系是否可以成立
“当前的话与前面的某些真的话冲突，就是假话；”
如果对于当前的话有矛盾的集合关系已经成立
(已经在同一集合)
那么这句话自然是假话
所以可以用并查集的思想来做
这里用到并查集是因为并查集的两个操作
“合并"可以变为一个集合的关系
“判断"在不在同一集合
所以综合以上思考
只需要把每一个动物都分成ABC三种考虑
然后对整体进行并查集操作即可
毕竟是找出假话
所以有的话只要不能判断是错的
便可以把它当成对的
故可以把全部的情况都综合来进行考虑
(也就是说到最后判断出的“假话”是那些一定错的话)
此处把
1N 设为 可能为A的情况
N+1N+N 设为 可能为B的情况
N+N+1~N+N+N 设为 可能为C的情况
需要注意的是ABC并非狭义上的固定种类
而是由于ABC都是假定的
所以不存在顺序问题
也就是内心把它理解为
1N 设为 可能为B的情况
N+1N+N 设为 可能为C的情况
N+N+1~N+N+N 设为 可能为A的情况
也未尝不可
主要是满足A->B->C->A的三角关系便可以了
这也是为什么程序里两个
关于 D==1 D==2 的if
只判断了 X
不需要对应判断 X+N X+2N 的原因
这一题需要注意的是在POJ上如果使用
while(scanf("%d %d",&N,&K)!=EOF) { }
也就是允许多次输入的话会WA
所以AC代码改成了只允许输入一次 N K
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
| #include<stdio.h>
int par[150150];
int rank[150150];
int find(int m) {
if(par[m]==m)
return m;
else
return par[m]=find(par[m]);
}
void unite(int x,int y) {
x=find(x);
y=find(y);
if(x==y)
return;
if(rank[x]<rank[y])
par[x]=y;
else {
par[y]=x;
if(rank[x]==rank[y])
rank[x]++;
}
}
int main() {
int N,K;
scanf("%d %d",&N,&K);
for(int i=1; i<=3*N; i++) {
par[i]=i;
rank[i]=0;
}
int cnt=0;
while(K--) {
int D,X,Y;
scanf("%d %d %d",&D,&X,&Y);
if(X<1||Y<1||X>N||Y>N) {
cnt++;
continue;
}
if(D==1) {
if(find(X)==find(Y+N)||find(X)==find(Y+N+N))
cnt++;
else {
unite(X,Y);
unite(X+N,Y+N);
unite(X+N+N,Y+N+N);
}
} else {
if(find(X)==find(Y)||find(X)==find(Y+N+N))
cnt++;
else {
unite(X,Y+N);
unite(X+N,Y+N+N);
unite(X+N+N,Y);
}
}
}
printf("%d\n",cnt);
return 0;
}
|
题目地址:
【POJ】[1182]食物链
因为POJ上述指出的判题问题
所以附一个NYOJ的地址
食物链
NYOJ这一题写成多组输入不会WA