| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 62824 | Accepted: 18432 |
Description
Input
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
大体思想：
1、如果两个物种有联系，不管是吃，被吃还是同类，它们之间应该是有一条径路可达的，也就是它们在一个合集中。
2、如果a,b有关系，b,c有关系，那么a,c之间的关系式可以通过两者的关系推出来的。
下面围绕着上面的两个思想来逐一拆分。
首先就是怎么把有关系的物种放到同一个合集中去,这就要需用到并查集了。每一次入输d,x,y， 也就是相当于x,y之间有一条权为d的径路。先忽略这个权值，直接斟酌路径，那并查集的路径建立就不用我说了。一个parent数组,parent[i]表现从parent[i]到i有一条径路。那不同的食物圈就构成了一个连通区域。每个连通区域都有一个根点节。
下面斟酌怎么处理这个权
先说点数学，任何一种偏序关系都足满自反、对称、传递。
自反：自己跟自己满足偏序关系。
对称：a,b的偏序关系为r，则b,a的偏序关系为~r.表现求反。
传递：a,b的偏序关系为r1，b,c的偏序关系为r2，a,c的偏序关系为r1+r2.
为了便利，用一个relation数组来维护这个权值。relation[i]表现的是i在所的连通区域的根点节到i的关系。先略忽这个关系数组的维护过程，把团体的思绪理清晰。如果有两个物种加进来， 就有两种情况，要么它们在同一个连通集里头。要么不在同一个连通集里头。
一、两者在同一个连通集里头：
1、新加的关系表明x,y是同类，那么它们两个分别到连通区域根点节的关系应该是一样的，要不就矛盾了。（记为case1）
2、如果新加的关系表明x,y不是同类，那么在当前参加y，x相对根节点的关系和x本来相对根点节的关系应该是不变的，否则就矛盾了。（记为case2）
二、两者在不同的连通集里头：就直接连接两个连通集就能够了。（记为case3）
路径压缩处理： 由于后来物种会越来越多，我们不希望食物链拉的很长，所以会尽可能的让全部的点节都直接和根节点 相连。这样整个连通的图就有点呈现出星形。
怎么维护关系数组： 数组里头的每个元素的取值要么是0（同类），要么是1（父吃子），要么是2（子吃父）。
至于为什么要这么设置（因为题目中1表示同类，而我们定义0表示同类，相对都应该减一，所以题目中的2表示父吃子在我们这里 应该是2-1=1，,1表示父吃子），参考一另篇博客http://blog.csdn.net/c0de4fun/article/details/7318642， 这里是不能随便定义的。设前面的数据我已经处理好了，现在要处理d,x,y.为了叙说的便利，
记relation[x]为x根->x.那么在现就有三种情况：
case1：（同一个集合且同类） 这种情况x根与y根雷同。如果x根->x与y根->y不同，表明x,y不是同类，与d=1矛盾。
case2：（同一个集合但不同类） 这种情况x根与y根雷同。如果参加y之后，（x根->x） = （x根（即y根）->y + y->x），如果新求出来 的关系与本身已有的x根->x的关系不同，则矛盾。
case3：（在不同集合中） 这种情况x根与y根不同。由于这里添加的是x到y的一条有向边。将y根的父点节设置为x根，更新y根父点 节到x根的关系，即x根->y根=x根->x+x->y+y->y根，由于这里都是有向边，所以更新关系的时候注意关 系的方向。这里需要注意，我们只更新了两个根之间的关系，x根与原来的y所在的连通区域里头的节点 的关系都没有更新，这就是为什么要在一开始判断之前就要调用Find函数，更新每个点节到其根点节的 关系。
初始条件： 有了这个递推，就好办了。初始条件parent就是并查集一般的初始条件，父点节于等自己。由于初始的 时候父节点是自己，当然自己跟自己的关系肯定是同类咯，也就是relation[i]=0
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int father[50005]; 6 int relation[50005]; 7 //int d; 8 9 void make_set(int n){ 10 for(int i = 0; i <= n; i++){ 11 father[i] = i; 12 relation[i] = 0; 13 } 14 } 15 16 //更新的步调，先将当前点节与其根点节相连，然后更新其与根点节的关系 17 //当前节点x与根节点r的关系更新的方法： 18 // (x与其父点节的关系+其父点节的关系与根点节的关系)%3 19 //所以在更新节点x的数据之前需要更新其父节点的数据，这是find为什么搞成递归函数的原因 20 //其更新的次序是从根节点开始往下，始终到当前点节x的父点节。 21 int GetParent(int x){ 22 if(x != father[x]){ 23 int t = father[x]; 24 //将当前点节的父点节设置为根点节 25 father[x] = GetParent(father[x]); 26 //更新当前节点与根节点的关系，由x->x父和x父->父根的关系是x->父根的关系 27 //所以在这之前必须更新其父点节与根点节的关系 28 relation[x] = (relation[x] + relation[t]) % 3; 29 //father[x] = GetParent(father[x]);//写在这是错的 30 31 } 32 return father[x]; 33 } 34 35 void Merge_set(int x, int y, int d){ 36 int fx = GetParent(x); 37 int fy = GetParent(y); 38 if(fx != fy){ 39 father[fy] = fx; 40 relation[fy] = (relation[x] + (d - 1) + (3 - relation[y])) % 3; 41 } 42 } 43 44 int main(){ 45 int n, k; 46 //cin >> n >> k; 47 scanf("%d %d", &n, &k); 48 int cnt = 0; 49 make_set(n); 50 while(k--){ 51 int d, x, y; 52 //cin >> d >> x >> y; 53 scanf("%d %d %d", &d, &x, &y); 54 55 if(x > n || y > n || (d == 2 && x == y)){ 56 cnt++; 57 continue; 58 } 59 60 int fx = GetParent(x); 61 int fy = GetParent(y); 62 63 if(fx == fy){//属于同一个子集 64 //如果x,y是同类，那么他们相对根节点的关系应该是一样的 65 if(d == 1 && relation[x] != relation[y]) 66 cnt++; 67 //如果不是同类，加入x和y的关系之后，x相对根节点的关系(x根->y,y->x(即3-(d-1)=2).即x根->x)应该是不变的 68 //这里d=2表示x - y = 2-1=1;而y->x=3-(x->y)=3-1=2; 69 if(d == 2 && relation[x] != (relation[y] + 2)%3) 70 cnt++; 71 } 72 else{ 73 Merge_set(x, y, d); 74 } 75 } 76 //cout << cnt << endl; 77 printf("%d ", cnt); 78 return 0; 79 }
用cin,cout会超时。。。