题目链接: http://poj.org/problem?id=1182
题意: 中文题就不用说了把~
思路: 带权并查集
把能确定关系的x, y 合并到并查集中;
我们可以用rank[x]记录x与其父亲节点的关系, 注意不是x与根节点的关系,是其与父亲节点的关系!!!
rank[x]=0表示x与其父亲属于同一个类;
rank[x]=1表示x的父亲吃x;
rank[x]=2表示x吃x的父亲;
1 #include <iostream>
2 #include <stdio.h>
3 #define MAXN 50010
4 using namespace std;
5
6 int rank[MAXN], pre[MAXN]; //***rank数组存储当前节点与父亲节点的关系!注意不是与根节点的关系!!!
7
8 int find(int x){//**递归路径压缩
9 if(pre[x]!=x){
10 int px=find(pre[x]);
11 rank[x]=(rank[x]+rank[pre[x]])%3; //***回溯时改变rank[x]的值,这个公式我们可以由枚举得出
12 pre[x]=px; //***将 x 的父亲节点变为根节点,即 x 节点直接指向根节点
13 }
14 return pre[x];
15 }
16
17 int jion(int x, int y, int d){
18 int px=find(x);
19 int py=find(y);
20 if(px==py){ //***若 x, y 都已经加入并查集,即相对关系已经确定,递归压缩路径后 x, y 的根节点即为他们的父节点, 我们可以由rank得到 x, y的关系,因为我们加入并查集的 x, y的关系都是真确的,所以如果d值与我们由rank得到的关系不同,那么其为假话
21 if((rank[y]-rank[x]+3)%3!=d){ //***x, y的关系我们可以由枚举得出
22 return 1;
23 }
24 }else{
25 pre[py]=px;
26 rank[py]=(rank[x]-rank[y]+d+3)%3; //***得到合并后px与py的关系,此处的公式也是可以通过枚举得出的
27 }
28 return 0;
29 }
30
31 int main(void){
32 int n, k, ans=0;
33 scanf("%d%d", &n, &k);
34 for(int i=0; i<MAXN; i++){
35 rank[i]=0;
36 pre[i]=i;
37 }
38 while(k--){
39 int d, x, y;
40 scanf("%d%d%d", &d, &x, &y);
41 if(x>n||y>n){
42 ans++;
43 }else if(d==2&&x==y){
44 ans++;
45 }else{
46 ans+=jion(x, y, d-1);
47 }
48 }
49 printf("%d
", ans);
50 return 0;
51 }