POJ 1182 食物链
做题感悟：这题如果不看解题报告真的不好做，但是网上的解题报告大部分是贴代码，不讲原理，在这里我结合我的理解+网上各位大牛的解题思路总结一下本题（如果冒犯某位大牛敬请谅解，如果总结有误请提出疑问）。
1、题意: 动物王国有三种动物 A B C 且存在 A吃B B吃C C吃A 一共N个动物。
给你一系列操作判断是否是真话：
1 x y // 代表 x 和 y 是同类
2 x y // 代表 x 吃 y
假话判断标准：
1）当前的话与前面的真话相冲突
2）当前的话中x 或 y 比N 大
3）当前的话表示x 吃x
2、解题思路：
这题必须把所有的动物放在一个集合里，那么必须依靠一种关系来标明个物种之间的关系。于是根据题意： 1 x y 2 x y 我们可以建立这样一个关系： 我们注意到，当 d = 1的时候，( d - 1 ) = 0，表示x y 同类 当 d = 2的时候，( d - 1 ) = 1，代表Y被X吃。
0 - > x 节点与父亲节点属于同类
1 - > x 节点被父亲节点吃
2 - > x 吃父亲节点
查找操作：
在查找时因为一个节点不仅要更新父亲的信息还要更新与父亲的关系的信息，即：T[x].parent 和T[x].relation 以前采用路径压缩时只是让父亲节点改为整个集合的祖先。
先看代码：
-
int find(int x)
-
{
-
if(T[x].parent!=x)
-
{
-
int temp=T[x].parent ;//存一下先前父亲
-
T[x].parent=find(temp) ;
-
T[x].relation=(T[x].relation+T[temp].relation)%3 ;// 依靠先前父亲节点更新
-
return T[x].parent ;
-
}
-
return T[x].parent ;
-
}
为什么是 T[x].relation = ( T[x].relation + T[temp].relation ) % 3 ; 我们可以用向量的方法来思考。我们可以把这种关系看成偏移量。
例如： x - > y 偏移量为 0 表示x 和 y 属于同类，
x - > y 偏移量为 1 说明 y 吃 x
x - > y 偏移量为 2 说明 y 吃 x.
这样的话更新子节点与祖先的关系就不难了。
假设： x - > rootx ( x 的父亲为 rootx ) rootx - > rootxx ( rootx 的父亲为 rootxx )
如果要确定 x 与 rootxx 的关系： x - > rootxx = x - > rootx + rootx - > rootxx ;(这里T[x].relation 代表x - > rootx 的关系,对3取余防止超过 2 ).
合并操作：
在将元素x 和y所在的集合合并时，假设元素x所在的祖先为rootx ，元素y所在的祖先为rooty，这里规定合并时直接将rooty指向rootx，即：T[rootx].parent=rootxy ;这样原来rooty所在的集合的元素与rootx的关系要改变（是不是要更新整个新合并的rootx集合呢? 其实不用,只要先更新rooty和祖先rootx的关系，其它的点在find()(查找操作)中就可以更新）。
1）如果x和y的祖先不相同即：x 与 y 的关系正确但是需要合并 x 和 y 所在的集合（关键）。这次合并同样用向量的概念： rootx - > rooty = rootx - > x + x - > y + y - > rooty （rootx->x 表示rootx对x的关系 即：T[x].relation y->rooty 表示y对rooty的关系 = 3-T[y].relatioin 可以举个例子：如果T[y].relation =1 表示y被rooty吃,而3-T[y].relation = 2 表示rooty吃y一个道理）即：3-T[y].relation+d-1+ T[x].relation .(PS：T[x].relation 为x的根节点到x的偏移量).
2）如果x和y的祖先相同，就需要判断x和y的关系是否正确。这里假设x和y的祖先同为rootxy 则x - > y = x - > rootxy + rootxy - > y 即判断：( 3 - T[x].relation + T[y].relation ) %3 是否等于 d - 1（d-1就是上面提到的y与x的关系）
代码：
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<stack>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
const double PI = 3.1415926 ;
-
const int INF = 99999999 ;
-
const int MX =50006 ;
-
int n,k,d,ans ;
-
struct node
-
{
-
int parent ; // 记录父亲节点
-
int relation ; // 记录根节点与当前节点的关系
-
}T[MX] ;
-
void init() // 初始化
-
{
-
for(int i=0 ;i<=n ;i++)
-
{
-
T[i].parent=i ;
-
T[i].relation=0 ;// 表示与父亲节点属于同一类（T[i].parent=i）
-
}
-
}
-
int find(int x)
-
{
-
if(T[x].parent!=x)
-
{
-
int temp=T[x].parent ;//存一下先前父亲
-
T[x].parent=find(temp) ;
-
T[x].relation=(T[x].relation+T[temp].relation)%3 ;// 依靠先前父亲节点更新
-
return T[x].parent ;
-
}
-
return T[x].parent ;
-
}
-
void union_find(int x,int y,int d)
-
{
-
int ax=find(x) ;// 寻找父亲
-
int ay=find(y) ;// 同上
-
if(ax!=ay) //不是同一个父亲 -> 合并 这里规定让 y 所在集合指向x所在集合
-
{
-
T[ay].parent=ax ; // rootx - > rooty = rootx - > x + x - > y + y - > rooty
-
T[ay].relation=(3-T[y].relation+d-1+T[x].relation)%3 ;// 先只改变父亲，孩子节点在find()中更新
-
}
-
else if((3-T[x].relation+T[y].relation)%3!=d-1) // 如果祖先相同判断关系
-
ans++ ;
-
}
-
int main()
-
{
-
int x,y ;
-
scanf("%d%d",&n,&k) ;
-
ans=0 ;
-
init() ;
-
for(int i=0 ;i<k ;i++)
-
{
-
scanf("%d%d%d",&d,&x,&y) ;
-
if(x>n||y>n||(d==2&&x==y)) // 判断 2 3 条件是否成立
-
{
-
ans++ ;
-
continue ;
-
}
-
union_find(x,y,d) ;// 判断条件 1
-
}
-
printf("%d\n",ans) ;
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/22484485
- 点赞
- 收藏
- 关注作者
评论（0）