题意为有三类动物,他们的食物链是环,即 A 吃 B, B 吃 C, C 吃 A。
给出一些动物的食物链关系,根据以前的关系,判断当前关系是否正确。
因为并查集是一棵森林,我们用一个数组 dist[i] 记录并查集的树中结点 i 与根的关系, 值为 1 表示吃根结点, 2 表示被根结点吃,为 0 表示两者为同一类动物。
对于输入的关系 d x y :
1). 如果 x, y 属于同一集合,判断两都关系是否合理,根据下图:
x, y 为同一集合, 所以 x, y 指向同一根。 x 与根 rt 的关系距离为 dist[x], y 与根 rt 的关系距离为 dist[y],
根据输入 x 与 y 的关系距离为 d。 由图有 d+ dist[y]== dist[x] ( mod 3 )。
2). 如果 x, y 不属于同一集合,根据下图有:
图中 x 与 rx 属同一集合,rx 的 x 的根, y 与 ry 原同一集合,ry 为 y 的根。 rx!= ry, x 与 y 不属于同一集合,这时应当将 x, y 合并,这里合并时将 rx 指向 ry, ry 成了新集合的根,根据图有:
d+ dist[y]== dist[x]+ dist[rx] --> dist[rx]= d+ dist[y]- dist[x] 求出了关系距离。
还有一个问题(就上图而言): x 与 y 合并后, ry 成了新集合的根,这时原来以 rx 为根的集合中的结点与 ry 的关系距离需要重新确定,如何确定:
假设并查集树为 x->a->b->rx ->ry, rx->ry 的关系距离已经求出,即 dist[rx] 已知, b 到 ry 的关系距离为 b 到 rx 的距离加上 rx 到 ry 的距离和。 故 dist[b]= dist[b]+ dist[rx]。 依次求出。
代码:
#include <stdio.h>
#include <stdlib.h>
int const N= 50010;
int n, k;
int uset[N], dist[N];
int find( int x ){
if( x== uset[x] ) return x;
int rt= find( uset[x] );
dist[x]= ( dist[x]+ dist[ uset[x] ] )% 3;
uset[x]= rt;
return rt;
}
int main(){
scanf("%d%d",&n,&k);
for( int i= 0; i<= n; ++i ){
uset[i]= i; dist[i]= 0; }
int ans= 0;
for( int i= 0; i< k; ++i ){
int d, x, y;
scanf("%d%d%d", &d, &x, &y ); d--;
if( x> n || y> n ){ ans++; continue; }
int rx= find(x), ry= find(y);
if( rx== ry ){
if( ( d+ dist[y] )% dist[x] ) ans++;
}else{
uset[rx]= ry;
dist[rx]= ( d+ dist[y]- dist[x]+ 6 )% 3;
}
}
printf("%d\n", ans );
return 0;
}
|
阅读(1940) | 评论(0) | 转发(0) |