posts - 10,  comments - 14,  trackbacks - 0

本来要先写搜索和DP的报告的,因为前面做的都是搜索和DP,正好昨天做了这道并查集的题目,所以就顺手写下。这道题也让我理解了好长时间,还是很有意义的,网上也没有很详细的解题报告。
题目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

因为我是按网上通用分类做的,所以做之前就知道用并查集做,不过这道题是并查集的深入应用,没有其它的那么直观。这里我采用的是和网上主流方法一样的方法,这里先贴出源码再深入解释下。


#include <iostream>
using namespace std;
struct point{
    int parent;
    int kind;
} ufind[50010];
void init(int n);
int find(int index);
void unions(int rootx, int rooty, int x, int y, int dkind);
int main()
{
    int n,k,count=0,d,x,y;
    scanf("%d%d",&n,&k);
    
        init(n);
        while(k--)
        {
            scanf("%d%d%d",&d,&x,&y);
            if(x>n || y>n)
                count++;
            else if(d==2 && x==y)
                    count++;
            else
            {
                int rx=find(x);
                int ry=find(y);
                if(rx!=ry)
                    unions(rx,ry,x,y,d-1);
                else
                {
                    if(d==1 && ufind[x].kind!=ufind[y].kind)
                        count++;
                    if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
                        count++;
                }
            }
        }
        printf("%d\n",count);
    
    
    return 0;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        ufind[i].parent=i;
        ufind[i].kind=0;
    }
}
int find(int index)
{
    int temp;
    if(index==ufind[index].parent)
        return index;
    temp=ufind[index].parent;
    ufind[index].parent=find(ufind[index].parent);
    ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
    return ufind[index].parent;
}
void unions(int rootx, int rooty, int x, int y, int dkind)
{
    ufind[rooty].parent=rootx;
    ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
}


1.这里并查集(ufind)的一个同类集合存放的是根据已有正确推断有关联的点,这里的关联包括了吃,被吃,同类三个关系;
2.关系是通过kind来表示的,其值为0,1,2,如果ufind[1].kind==ufind[2].kind,说明1,2点同类;如果
(ufind[1].kind-ufind[2].kind+3)%3==1,说明1吃2;
3.并查集是按索引部分组织起来的,即同一类的点都有共同的根结点;
4.并查集包括初始化(init),查找(find),合并(unions)操作,其中有很多关键点,我都在代码中用红色标记。下面逐一解释这些关键点:
(1)ufind[i].kind=0;种类初始化为0,这个看似很简单,但它其实保证了并查集中每一个类的根结点的kind属性为0,这是后面两个关键式推导的基础;
(2)ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;这句出现在合并操作里面,这里要解释的是,在合并之前每个类的集合中所有父节点为根结点的点以及根结点,它们之间的关系都是正确的,合并之后只保证了合并前原两个集合的根结点之间的关系正确,即在新的合并后的集合中仍保证所有父节点为根结点的点以及根结点之间的关系正确。这样我们在做合并操作时,是通过三个关系推到出预合并的两个根结点(rootx,rooty)之间的正确关系的:x和rootx的关系,y和rooty的系,x和y的关系。这就是这个式子的由来,其中用到了前面说过的rootx和rooty为0的结论。
(3)ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;这句出现在查找操作里,作用是将待查找的点到它的根结点所经过的所有点进行两个操作,一是把它们的父节点都设为根结点;二是按照从离根结点最近的那个点开始到待查找的点的顺序把它们与根结点的关系设置成正确值(原先有可能是错误的,因为合并操作只保证了所有父节点为根结点的点以及根结点之间的关系正确)。这样之后这个集合中仍然保证了所有父节点为根结点的点以及根结点之间的关系正确,并且待考察的点的父节点为根结点。下面来解释下为什么要按照从离根结点最近的那个点开始到待查找的点的顺序,这也是这个式子为什么这么写的原因:假设1为根结点,Kind为0,其子节点为2,kind为k2,2的子节点为3,kind为k3;因为每次合并只合并根结点,所以3在1,2合并前的根结点一定是2,即若2的kind为0,则3和2的关系就正确了,但合并时2的kind加上了k2,保证了1与2的关系正确而并没有更新k3(这是因为并查集集合中无法从父节点找到子结点,所以等到查找时,要用到该点时再更新也不迟),所以此时只要将(k2+k3)%3就可以得到正确的以1为基准的3的kind。接下来,k3的kind修正了,k4可以以k3为基础一样通过此方法修正,直到要查的结点,并把它们全部挂到根结点上。
解释就到这里,我想理解时只要画个图就能容易理解些,即以index和kind为结点做出集合的树状图。这里恰巧是3个关系,若是4个关系我想就要更新并查集单位集合的组织形式了,即要可以从根结点遍历全集和。

posted on 2009-05-23 11:53 tortoisewu 阅读(4857) 评论(8)  编辑 收藏 引用

FeedBack:
# re: poj 1182 解题报告
2009-05-23 13:30 | E剑仙
并查集经典题  回复  更多评论
  
# re: poj 1182 解题报告
2009-05-30 19:23 | whr
你的用红线标识的关系怎么推得? 这其间的关系并不是很明朗......  回复  更多评论
  
# re: poj 1182 解题报告
2009-05-30 22:28 | tortoisewu
建议你画个图理解下会容易很多。
先说下合并函数中的关系,因为在合并函数之前先进行了查找函数,而在查找函数中已压缩了路径,即把查找的点到根结点路径上所有点都挂到了根结点下,并更新了它们kind的值,保证kind值是正确的(在这之前是不正确的);所以在合并函数中x,y,rootx,rooty的kind值在它们原先的集合中都是正确的,在合并时,要将rooty挂到rootx上,并只更新rooty的kind值以保证rooty在新的集合中kind值正确,而不必管rooty原先集合的其它结点kind值(没法管,因为并查集只能从叶节点遍历到根结点,无法向下遍历,将会放到find函数中更新)。更新的依据是三个关系:x和y的关系,x和rootx关系,y和rooty关系;对于这题就一定能得到rootx和rooty的关系,以更新对rooty在新的集合中的kind值。
如果你能理解了合并函数,那查找函数便可以推得,因为我们合并时只更新了挂在根结点上的原先集合根结点的kind值,所以这里要把查找路径上所有的点先挂到根结点上,并更新其kind值(也就是每个集合深度为1的结点的kind值都是正确的)。更新顺序一定要是从深度低的到深度高的,因为更新依据要依赖当前结点的原kind值和其父节点的更新后的kind值。为什么是上述给出的两个值的和的关系呢?因为在合并前根结点的kind都为0,所以合并后原被合并集合深度为1的点的kind值只要加上更新后原其根结点的kind值就能得到正确关系了。一定要画图理解,模拟下过程,结合我红色标识的三个式子一起理解。我还有篇总结也许有帮助http://www.cppblog.com/tortoisewu/archive/2009/05/29/86110.html@whr
  回复  更多评论
  
# re: poj 1182 解题报告
2009-07-14 16:10 | Guest
主函数中 if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
count++;
条件应该是 (ufind[x].kind-ufind[y].kind+3)%3 != 2 吧

0->1->2->0 吃的关系相差 -1 或 2, 取模后是 2
建议楼主看一下  回复  更多评论
  
# re: poj 1182 解题报告[未登录]
2009-09-15 13:11 | chris
最后一句什么意思?  回复  更多评论
  
# re: poj 1182 解题报告
2009-10-08 11:40 | blackstar
怎么证明你的公式的正确性了?  回复  更多评论
  
# re: poj 1182 解题报告
2010-02-01 01:25 | 匿名
这里0,1,2不代表具体的种类,而是如果(ufind[x].kind-ufind[y].kind+3)%3==1,说明x吃y,是一个相对关系。即只通过0,1,2的相对关系表示同类,吃,被吃三种关系,不与具体类别对应,kind为0的可能是3种的任意一种@Guest
  回复  更多评论
  
# re: poj 1182 解题报告
2010-04-05 21:03 | monday41
在union时,为什么秩合并会WA
void unions(int rootx, int rooty, int x, int y, int dkind)
{
if(rank[rootx]>rank[rooty])
{
ufind[rooty].parent=rootx;
rank[rootx]+=rank[rooty];
}
else
{
ufind[rootx].parent=rooty;
rank[rooty]+=rank[rooty];
}
ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
}   回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(1)

随笔档案

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜