- 浏览: 196579 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
建议:做此题之前先做 poj 2524 和 poj 1611。这两道题都是并查集的基础应用。
关键词:并查集 相对关系
思路:(用一个并查集就够了,同时对每个节点保持其到根结点的相对类别偏移量)
1.father[x]表示x的根结点。rank[x]表示father[x]与x的关系。rank[x] == 0 表示father[x]与x同类;1表示father[x]吃x;2表示x吃father[x]。
2.怎样划分一个集合呢?
注意,这里不是根据x与father[x]是否是同类来划分。而是根据“x与father[x]能否确定两者之间的关系”来划分,若能确定x与father[x]的关系,则它们同属一个集合。
3.怎样判断一句话是不是假话?
假设已读入 D , X , Y , 先利用find_set()函数得到X , Y 所在集合的代表元素 xf ,yf ,若它们在同一集合(即 xf == yf )则可以判断这句话的真伪( 据 2. ).
若 D == 1 而 rank[X] != rank[Y] 则此话为假。(D == 1 表示X与Y为同类,而从rank[X] != rank[Y]可以推出 X 与 Y 不同类。矛盾。)
若 D == 2 而 rank[X] == rank[Y] (X 与Y为同类)或者 rank[X] == ( rank[Y] + 1 ) % 3 (Y吃X )则此话为假。
4.上个问题中 r[X] == ( r[Y] + 1 ) % 3这个式子怎样推来?假设有Y吃X,那么r[X]和r[Y]的值是怎样的?
我们来列举一下: r[X] = 0 && r[Y] = 2
r[X] = 1 && r[Y] = 0
r[X] = 2 && r[Y] = 1
稍微观察一下就知道r[X] = ( r[Y] + 1 ) % 3;事实上,对于上个问题有更一般的判断方法:
若 ( r[Y] - r[X] + 3 ) % 3 != D - 1 ,则此话为假。(来自poj 1182中的Discuss )
5、注意事项:
A、我们用x--r-->y表示x和y之间的关系是r,比如x--1--y代表x吃y。现在,若已知x--r1-->y,y--r2-->z,如何求x--?-->z?,于是我们不难发现,x--(r1+r2)%3-->z。这个就是在Find_Set(int x)函数中用到的更新x与father[X]的关系
B、当D X Y时,则应合并X的根节点和Y的根节点,同时修改各自的rank。那么问题来了,合并了之后,被合并的根节点的kind值如何变化呢?
现有x和y,d为x和y的关系,xf和yf分别是x和y的根节点,于是我们有x--rank[x]-->xf,y--rank[y]-->yf,显然我们可以得到xf--(3-rank[x])-->x,yf--(3-rank[y])-->y。假如合并后x为新的树的根节点,那么原先fx树上的节点不需变化,yf树则需改变了,因为rank值为该节点和树根的关系。这里只改变rank(yf)即可,因为在进行find_set操作时可相应改变yf树的所有节点的kind值。于是问题变成了yf--?-->xf。我们不难发现yf--(3-rank[y])-->y--(3-d)-->x--rank[x]-->xf,根据前面的结论,我们有yf--(3-rank[y])-->y--(3-d)-->x--rank[x]-->xf。我们求解了xf和yf的关系了。
代码如下:
#include <iostream>
const int MAX=50005;
int father[MAX];
int rank[MAX];
//初始化集合
void Make_Sent(int x)
{
father[x]=x;
rank[x]=0;
}
//查找x的集合,回溯时压缩路径,并修改x与father[x]的关系
int Find_set(int x)
{
int t;
if(x!=father[x])
{
t = father[x];
father[x]= Find_set(father[x]);
//更新x与father[X]的关系
rank[x] = (rank[x]+rank[t])%3;
}
return father[x];
}
//合并x,y所在的集合
void Union(int x,int y,int d)
{
int xf = Find_set(x);
int yf = Find_set(y);
//将集合xf合并到yf集合上
father[xf] = yf;
//更新 xf 与father[xf]的关系
rank[xf]=(rank[y]-rank[x]+3+d)%3;
}
int main()
{
int totle=0;
int i,n,k,x,y,d,xf,yf;
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
Make_Sent(i);
while(k--)
{
scanf("%d%d%d",&d,&x,&y);
//如果x或y比n大,或x吃x,是假话
if(x>n||y>n||(d==2 && x == y))
{
totle++;
}
else
{
xf = Find_set(x);
yf = Find_set(y);
//如果x,f的父节点相同 ,那么可以判断给出的关系是否正确的
if(xf == yf)
{
if((rank[x]-rank[y]+3)%3 != d-1)
totle++;
}
else
{
//否则合并x,y
Union(x,y,d-1);
}
}
}
printf("%d\n",totle);
system("pause");
return 0;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 786虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 783选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 809题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 945题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
poj 2492
2012-08-04 16:23 2004题意:Professor Hopper专门研究bug的生活习性 ... -
字典树学习材料
2012-05-30 14:29 932字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1396题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 975大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1570题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2670是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1206在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 775从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2350题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1062题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1226大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 962题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2116大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1221题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ...
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码