poj 1182 食物链 带权并查集模板题

缘起

日常水题 poj 1182 食物链 作为带权并查集的模板.

分析

题目是中文的.

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
动物王国中有三类动物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。 
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 
1） 当前的话与前面的某些真的话冲突，就是假话； 
2） 当前的话中X或Y比N大，就是假话； 
3） 当前的话表示X吃X，就是假话。 
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。 

【输入】
第一行是两个整数N和K，以一个空格分隔。 
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。 
若D=1，则表示X和Y是同类。 
若D=2，则表示X吃Y。

【输出】
只有一个整数，表示假话的数目。

【样例输入】
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

【样例输出】
3

【限制】
Time limit 1000 ms
Memory limit 10000 kB

【来源
Noi 01

带权并查集模板题, 不熟悉这种数据结构的同学可以参见【1】

此题又是一道好题——想清楚了就很简单，没想到思路，代码会写的非常混乱.

因为本题除了考虑是否属于一类，还要考虑捕食关系. 所以对于一个动物x，我们考虑将其扩倍为(x,A),(x,B),(x,C)三个元素. 则如果遇到了x和y属于同一类的说法，则考虑merge ((x,A),(y,A))、((x,B),(y,B))、((x,C),(y,C)) 三种并查集关系.

类似的, 如果遇到了 x吃y的说法, 则考虑merge ((x,A),(y,B))、((x,B),(y,C))、((x,C),(y,A)) 三种并查集关系.

但是什么时候是谎话呢? 就是无法merge的时候（例如, 你打算merge (x,A)和(y,A), 但是发现(x,A)和(y,B)已经在一个并查集中了， 即爹一样）. 因为如果x和y属于同类这种说法是真话, 则上述三种并查集关系—— ((x,A),(y,A))、((x,B),(y,B))、((x,C),(y,C)) 是都能merge成功的. 如果不是真话，则上述三种并查集关系都不能merge成功的. 为什么? 因为

如果x与y是谎言，则 ((x,A),(y,A))、((x,B),(y,B))、((x,C),(y,C)) 至少一对不能merge成功.

比如(x,A)和(y,A)merge失败，说明(x,A)和(y,B)已经在一个集合中，说明还已经merge过(x,B)(y,C)以及 (x,C)(y,A)(这是代码实现细节上保证的), 而后两者将导致(x,B)(y,B)与(x,C)(y,C)merge的失败. 所以三者都会merge失败. 反之，如果x与y同类是真话，则三者至少一个能merge成功，则必须要都成功，不然根据刚才的推理，三个都不能成功. 所以一句话的真假等价于三者中至少一个能merge成功（其实也等价于三者都要merge成功） 有了这个判定准则，就不难写下下面的代码，

技术上，我们用[0,N) 存储(x,A)们, [N,2N)存储(x,B)们, [2N,3N)存储 (x,C)们

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
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,k,f[150005],d,x,y; // f是带权并查集, f[i]如果<0,则表示i是该树的根节点, 并且该树的元素个数是-f[i]

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]); // 找爹
}

void merge(int i, int j) // 合并x和y
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj) // 
	{
		return;
	}
	if (f[fi]<f[fj]) // 如果i所在的树更加庞大, 则将j所在的树合并入i所在的树
	{
		f[fi]+=f[fj];
		f[fj] = fi;
	}
	else
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(f, -1, sizeof(f)); // f[i]表示i所在的并查集树中元素的个数
	scanf("%d%d", &n, &k);
	int ans = 0;
	while(k--)
	{
		scanf("%d%d%d", &d, &x, &y);
		if (x>n||y>n) // 如果越界,肯定非法
		{
			ans++;
			continue;
		}
		x--,y--; // 让x和y进入[0,n)这种范围 
		if (d==1) // 如果是x和y同类的说法, 准备插入 ((x,A),(y,A))、((x,B),(y,B))、((x,C),(y,C))三对并查集
		{
			if (getf(x)==getf(y+n)||getf(x)==getf(y+(n<<1))) // 如果已经存在了(x,A)(y,B)或者 (x,A)(y,C)， 则(x,A)与(y,A)将merge失败, 这是谎言
			{
				ans++;
				continue;
			}
			merge(x,y);
			merge(x+n,y+n);
			merge(x+(n<<1), y+(n<<1)); // 合并 ((x,A),(y,A))、((x,B),(y,B))、((x,C),(y,C)) 
		}
		else // 如果是x吃掉y的说法
		{
			if (getf(x)==getf(y) || getf(x)==getf(y+(n<<1))) // 如果已经存在了(x,A)(y,A)或者 (x,A)(y,C)， 则(x,A)与(y,B)将merge失败, 这是谎言
			{
				ans++;
				continue;;
			}
			merge(x,y+n);
			merge(x+n,y+(n<<1));
			merge(x+(n<<1), y); // 合并 ((x,A),(y,B))、((x,B),(y,C))、((x,C),(y,A)) 
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 250ms
Memory 676kB
Length 1401
Lang C++
Submitted 2019-08-21 13:39:00
Shared
RemoteRunId 20779887

参考

【1】https://yfsyfs.github.io/2019/05/25/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91-MST-%E4%B9%8BKruskal%E7%AE%97%E6%B3%95/