食物链poj1182 （超级经典的带权并查集）

食物链
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 108553 Accepted: 32935
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倍的虚拟节点做的，但是总感觉没有抓住带权并查集的特点，第二次是在看带权并查集详解的时候看到这题了，跟着详解做的，但是公式不是自己推的，第三次就是昨天晚上花了一个晚上，公式都是自己一步步推出来的，最后终于ac了。
这个题有四个公式是比较难的：

在此之前，因为有三种关系，我们定义一个数组：r[maxn],r[i]=0表示r[i]和根节点是同类，r[i]=1表示被根节点吃，r[i]=2表示吃根节点。

int find(int x){
	if(x!=f[x]){
		int t=f[x];
		f[x]=find(f[x]);
		r[x]=(r[x]+r[t])%3;
	}
	return f[x];
}

那么这个公式要解决什么问题呢，一张图

这个公式主要解决并查集路径压缩时候怎么根据字节点和父节点推关系推出子节点和祖宗节点关系。
这个公式还是比较容易推的，只需要画三个节点，在知道子节点和父节点的情况下如何推出字节的和祖宗节点的关系。
用枚举的方法，因为根节点只能是0，所以画一个真值表：

一般题目给出几个状态最后我们%几个状态，为了不让这个关系超出范围，这个公式稍微花一时间是可以推出来的。这样就把子节点与祖宗节点关系的压缩路径公式推出了了。

第二个公式，这个也是用枚举的办法推出来的，一开始我只推了d=1的情况没考虑d==2，因为我觉得因该是一样的，结果wa了，洗澡的时候又想了一下，突然发现d == 1 和 d == 2的合并公式是不一样的。
那么这个公式主要是解决什么问题呢？一张图：

网上说用向量去考虑那么公式是这样的：
r[fx]=-(r[x]+d+r[y])%3
和我自己推的公式是差不多不过缺了常数，所谓的向量方式不过就是用枚举的思想。
当d == 1表示表示xy是同类，我通过枚举推了一个公式：

当d == 2的时候也是枚举出来的公式这里就不写了。

                  f[fx]=fy;
                  if(d==1)
                  r[fx]=(r[y]-r[x]+d+2)%3;
                  if(d==2)
                  r[fx]=(r[y]-r[x]+d+3)%3;

第三个公式是用来判断x和y是否是同类，当他们不是同类ans++，这个公式还是比较简单的，如果他们是同类r[x]==r[y]这个稍微想象一下就懂了，

if(d==1&&r[x]!=r[y]){
				ans++;
			}

最后这个公式应该很多人看不懂，我也是其实也是枚举出来的，画一棵树把r[x]和r[y]全部可能的取值结果枚举出来，最后就会是这样了，要配合图形一起考虑，当r[x]或者r[y]为0 只有可能是其中一个是根节点，因为在同一棵树上，只有根节点的父亲节点是自己，当r[x]!=0 并且r[y]!=0这个时候就是说他们都不是根节点，然后根据关系推一下就行了。

if(d==2){
				if((r[x]==0&&r[y]!=1)||(r[x]==1&&r[y]!=2)||(r[x]==2&&r[y]!=0)){
					ans++;
				}	
			}

总之这道题受益匪浅弄懂了很多东西，其主要思想还是枚举。
ac代码：

#include<iostream>
using namespace std;

const int maxn=1e4+10;
int n,k,d,x,y;
int r[maxn*5];//用数组描述三种关系r[i]=0;当前节点与根节点是同类，=1：被根节点吃 
//根节点 ==2吃根节点
int f[maxn*5]; 
int find(int x){
	if(x!=f[x]){
		int t=f[x];
		f[x]=find(f[x]);
		r[x]=(r[x]+r[t])%3;
	}
	return f[x];
}
int main(){
	int ans=0;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		f[i]=i;r[i]=0;
	}
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&d,&x,&y);
		if(x>n||y>n||(d==2&&x==y)){ans++;continue;}
		int fx=find(x);
		int fy=find(y);
		if(fx!=fy){//只有不在同一棵树里面才能建立关系 
			f[fx]=fy;
                        if(d==1)
			r[fx]=(r[y]-r[x]+d+2)%3;
                        if(d==2)
                        r[fx]=(r[y]-r[x]+d+3)%3;
		}else{//检查关系是否正确 
			if(d==1&&r[x]!=r[y]){
				ans++;
			}
			if(d==2){
				if((r[x]==0&&r[y]!=1)||(r[x]==1&&r[y]!=2)||(r[x]==2&&r[y]!=0)){
					ans++;
				}	
			}
		} 
	}
	if(ans==0){
		cout<<"0"<<endl;
	}else{
		cout<<ans<<endl;
	}
}