食物链
Time Limit:1000MSMemory Limit:10000K
Total Submissions:49310Accepted:14382
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 71 101 1 2 1 22 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3分析：之前做过很多基础并查集，然后带权并查集，再就是种类并查集，某君说还要有异或并查集，马甲。在练带权并查集时就云里雾里，当时马马虎虎的就过了，这回我真心想重新捡起来，清清楚楚的研究透了，因为以前就是浪费学了白学，过完年就忘的一清二楚了，之前做过很多有意思的带权并查集，由于，急功近利没有真正的搞明白，搞熟练，现在都忘了。搞学习就是这样，，特别是acm包括计算机其他的，必须脚踏实地，不然就是欺骗自己，做欺骗自己的事毫无意义，最终一无所获。希望这些话对诸位有帮助。好吧，就这到题吧：这是一个典型的种类并查集，说是种类并查集，然正如某君所说“不要说种类并查集和带权并查集不一样”。首先定义：B是A的父节点即B=fa[A],若A与B同类则level[A]=0,若A吃B则level[A]=2,若A被B吃则level[A]=2;那么在判断是如果(level[B]-level[A]+3)%3!=d-1则为假话。如果 fx=Find(A),fy=Find(B),A,B不属于同一集合则fa[fy]=fx,level[fy]=(level[x]-level[y]+(d-1)+3)%3;所以种类并查集核心就是导出这些关系。在此之前我画和很多颗树，用了不同的关系式做出了这道题，于是总结出了一句话就是：种类并查集与向量有关，它的导出式就是向量的计算式。好，那我们就来演示一下为什么导出了上述公式。~首先已自定义了：B是A的父节点即B=fa[A],若A与B同类则level[A]=0,若A吃B则level[A]=2,若A被B吃则level[A]=2;为了方便设type=d-1；一、路径压缩假设有一个集合A-B-C-D;A是集合顶点(root)，则向量BA=level[B],CB=level[C],DC=level[D];(有子节点指向父节点)；则在压缩路径时需要更新所有的值(fa,level)。各位想压缩后的关系是：A-B，A-C，A-D，即直接指向集合顶点，fa[B]=A,fa[C]=A,fa[D]=A,这时level的计算是根据向量的计算来的，向量按照压缩路径的过程：BA=BA <=> level[B]=level[B],CA=BA+CB <=> level[C]=level[B]+level[C],DA=BA+CB+DC <=> level[D]=level[B]+level[C]+level[D];因为压缩是在Find函数回溯是压缩的，所以level[B]在level[C]之前更新，所以同理上式实际为level[B]=level[B];level[C]=level[B]+level[C];level[D]=level[C]+level[D];其实就是 level[x]=level[x]+level[fa[x]];为了防止溢出该式改为：level[x]=(level[x]+level[fa[x]]+3)%3;二、合并集合假设type B D,开始B,D属于不同集合,B属于A-B,D属于C-D,因此要合并这两个集合;type 为B D之间的关系数(题目中type=d-1)用向量表示DB=type由一、知向量BA=level[B],向量DC=level[D],先要把C-D并成A-B的子树;则fa[C]=A和并完成,于此同时还要更新level[C]的值;由于A成了C的子节点所以level[C]=CA=BA+DB-DC=type+level[x]-level[y];其实就是：level[fx]=level[x]-level[y]+type;为防止溢出上式改为 level[fx]=(level[x]-level[y]+type+3)%3;三、验证假设X Y在同一集合中验证type X Y是否正确(type=d-1);假设type X Y正确即YX=type=rY-rX=level[Y]-level[X];(r为此集合顶点);为防止溢出上式改为type=(level[Y]-level[X]+3)%3;若不想等则为假话;至此这道题的核心讲完了。各位“~首先已自定义“这地地方可以自己定义，不一定这样设，但我觉得0,1,2这三个数比较简单，也可以A吃B时level[A]=1啊(B=fa[A]),但是无论怎样万变不离宗、向量的特性是不变的。这是我对这道题和种类并查集的理解，下面献上代码：#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;const int maxh=50000+10;int fa[maxh],level[maxh],n,m;void Init(int num){ for(int i=0;i<=num;i++) { fa[i]=i; level[i]=0; }}int Find(int x){ if(x!=fa[x]) { int tmp=Find(fa[x]); level[x]=(level[x]+level[fa[x]])%3; fa[x]=tmp; } return fa[x];}bool Union(int x,int y,int type){ int fx=Find(x); int fy=Find(y); if(fx==fy) { if(((level[y]-level[x]+3)%3)!=type) return false; return true; } else { fa[fy]=fx; level[fy]=(level[x]-level[y]+type+3)%3; return true; }}int main(){ int x,y,type,sum; scanf("%d%d",&n,&m); Init(n); sum=0; for(int i=0;i<m;i++) { scanf("%d%d%d",&type,&x,&y); if(x>n||y>n) { sum++; continue; } if(type==2&&x==y) { sum++; continue; } if(!Union(x,y,type-1)) sum++; } printf("%d\n",sum); return 0;}
文画音，看似耳目所为，其实是内心世界的感受。
