pku 1182

 2009年7月12日 星期日

题目链接：PKU 1182 食物链
 
分类：并查集的拓展（经典）


题目分析与算法模型

        本题是一道经典的并查集的拓展，其中比较一般的解法是设立三个group，因为一共有三种动物。但其实有一种更加简便的方法，具体如下，利用向量的思考模式将三个group合并成一个并查集，同时对每个节点保持其到根结点的相对类别偏移量，定义为：
0——同类；
1——食物；
2——天敌；
对于树中的每一个节点（动物），记录其与根节点的相对偏移量，即上面的0，1和2，这样就可以根据相对平移量计算出其和根节点所代表的动物的关系，合并节点时，注意两棵树的根节点之间的相对偏移量，这里有几个公式需要自己推导，都在代码中了；

Code：

 1#include<stdio.h>
 2#define max 50005
 3
 4int n,k,i,j,parent[max],kind[max],count,a,b,d;
 5
 6void init(int n)
 7{
 8    for(j=1;j<=n;j++)
 9    {
10        parent[j]=-1;
11        kind[j]=0;
12    }
13}
14int find(int x)
15{
16    int t=parent[x];
17    if(t<0)return x;
18    parent[x]=find(t);
19    kind[x]=(kind[x]+kind[t])%3;
20    return parent[x];
21}
22void Union(int x,int y,int d)
23{
24    if(x>n||y>n)count++;
25    else if(d==1)
26    {
27        int root1=find(x),root2=find(y);
28        if(root1==root2)
29        {
30            if(kind[x]!=kind[y])count++;
31        }
32        else
33        {
34            if(parent[root1]<parent[root2])   //root1为根
35            {
36                parent[root1]+=parent[root2];
37                parent[root2]=root1;
38                kind[root2]=(kind[x]-kind[y]+3)%3;       //需要自己推导
39            }
40            else                              //root2为根
41            {
42                parent[root2]+=parent[root1];
43                parent[root1]=root2;
44                kind[root1]=(kind[y]-kind[x]+3)%3;
45            }
46        }
47    }
48    else   //d=2
49    {
50        if(x==y)count++;
51        else
52        {
53            int root1=find(x),root2=find(y);
54            if(root1==root2)
55            {
56                if(kind[x]!=(kind[y]+1)%3)count++;  //需要自己推导
57            }
58            else
59            {
60                if(parent[root1]<parent[root2])   //root1为根
61                {
62                    parent[root1]+=parent[root2];
63                    parent[root2]=root1;
64                    kind[root2]=(kind[x]-kind[y]+5)%3;       //需要自己推导
65                }
66                else                              //root2为根
67                { 
68                    parent[root2]+=parent[root1];
69                    parent[root1]=root2;
70                    kind[root1]=(kind[y]-kind[x]+4)%3;      //需要自己推导
71                }
72            }
73        }
74    }
75}
76int main()
77{
78    scanf("%d%d",&n,&k);
79    init(n);
80    count=0;
81    for(i=0;i<k;i++)
82    {
83        scanf("%d%d%d",&d,&a,&b);
84        Union(a,b,d);
85    }
86    printf("%d\n",count);
87    return 0;
88}
89

posted on 2009-07-13 00:08 蜗牛也Coding 阅读(1186) 评论(3)  编辑 收藏 引用

评论

# re: pku 1182[未登录] 2009-12-17 12:12 YY

YTE   回复  更多评论   

# re: pku 1182 2010-02-12 16:04 Y

大家注意了，那个1代表根是这个节点的食物，别误解了  回复  更多评论   

# re: pku 1182[未登录] 2010-03-26 19:15 菜鸟

可以简单说一下这几条语句什么意思么？
kind[x]=(kind[x]+kind[t])%3;
kind[root2]=(kind[x]-kind[y]+3)%3;
kind[root2]=(kind[x]-kind[y]+5)%3;
  回复  更多评论   


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜