[POJ 1182] 食物链【并查集】

  • 2018-01-04
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 10000K

Description

动物王国中有三类动物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),输出假话的总数。

Input

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

Output

只有一个整数,表示假话的数目。

Sample Input

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Sample Output

3

Source

Noi 01

Solution:

## 又一句题外话,昨天刚说 POJ 上难得见到中文题,结果立马又来了一道。。##

种类并查集的一道经典题。

用 0 ~ 2 表示三种动物的相对关系,其中 0 吃 11 吃 22 吃 0。之后的推导均以此为核心

于是我们可以用 rel[i] 表示并查集中 i 与其父节点 fa[i] 的关系。

路径压缩递归退出时,更新 rel[u] = (rel[u] + rel[fa[u]]) % 3,将其与父节点的关系转化为其与父节点的父节点(是否应称为爷爷节点?),即根节点的关系,然后再将其父节点 fa[u] 设置为根节点,从而维护了 rel[] 的正确性。

判断说法正确与否时,我们用 relat 表示说法中动物的关系,其中 0 表示同类,1 表示前者吃后者,则易得 relat = D - 1。

如果两种动物 u, v 的祖先相同,则它们的关系已经在之前的说法中确定,那么必须满足 rel[v] == (rel[u] + relat) % 3 才是真话。

如果两种动物 u, v 的祖先不同,则它们的关系不明确,这种说法被默认为正确,通过合并操作 union() 可以将关系添加到并查集中。

添加关系时,考虑到要使结果中 rel[v] == (rel[u] + relat) % 3,而通过寻找操作 find() 后 u, v 的父节点就是其祖先 ancu, ancv。我们可以固定每次将 ancv 连到 ancu 的子树下,那么也很容易推出此时关系的更新为 rel[ancv] = (rel[u] - rel[v] + relat + 3) % 3。

路径压缩的并查集时间复杂度:

  • O(N+Kα(K)),其中 α() 为反 Ackerman 函数,对于任意“可以想象”的正整数 x,总有 α(x) ≤ 4。

Code: O(N+Kα(K)) [556K, 250MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, K, ans = 0;
int fa[50005], anc;
int rel[50005];  // Record the relation between i and fa[i]

inline void ds_init() {for(register int i = 1; i <= N; i++) fa[i] = i;}

inline int ds_find(int u){
	if(fa[u] == u) return u;
	anc = ds_find(fa[u]);  // Find ancestor
	rel[u] = (rel[u] + rel[fa[u]]) % 3;
	return fa[u] = anc;
}

inline bool ds_union(int u, int v, int relat){
	int ancu = ds_find(u), ancv = ds_find(v);
	if(ancu == ancv) return rel[v] == (rel[u] + relat) % 3;  // Former statements have mentioned
	else{
		fa[ancv] = ancu;
		rel[ancv] = (rel[u] - rel[v] + relat + 3) % 3;
		// Infer this formula for a purpose of setting (rel[u] + relat) % 3 == rel[v]
		return true;  // Never mentioned before
	}
}

int main(){
	scanf("%d%d", &N, &K);
	ds_init();
	for(register int i = 1; i <= K; i++){
		int D, X, Y;
		scanf("%d%d%d", &D, &X, &Y);
		if(X < 1 || X > N || Y < 1 || Y > N) {ans++; continue;}
		if(!ds_union(X, Y, --D)) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai