首页 > Web开发 > 详细

DisJSet:食物链(POJ 1182)

时间:2015-10-01 19:10:16      阅读:370      评论:0      收藏:0      [点我收藏+]

                          技术分享

                动物王国的食物链

  题目是中文的,我就不翻译了,也很好理解,就是一个A-B-C-A的一个循环的食物链,给定一些条件,问你哪些条件是错的

  这一题,是一道比较经典的查并集的题目,那么这一题的思想是什么呢,对于给定的条件,x和y属于什么集合其实并没有给出,而且x和y之间还有其他的捕食的关系

  但是我们现在假设,如果x和y都是属于同一类的,那么如果x属于A,那么y也一定属于A,那么也就是说,x和y属于同一个集合总是同时成立的的,再假设,如果x可以吃y,那么如果x属于A,那么y一定属于B,x属于B,那么y一定属于C或x属于C,那么y一定属于A,也就是说,在捕食关系中,y属于x的下一个集合一定成立的(A-B-C-A)

  那么我们就可以用查并集来很好的维护这个关系,我们给x和y赋予A,B,C三个属性,并且用查并集来维护这些属性,如果x和y都属于一个集合,那么我们就要分别合并x和y的三个属性,如果属于不是关系,那么我们就把y的与x的下一个关系的集合进行合并,这三个属性可以用k,k+N,k+2*N的形式表现,这样就可以非常快速的维护关系了(因为对于找根的操作而言,查并集是最快的)

  参考《挑战程序设计竞赛 第二版》

  PS:查并集我用的是按大小合并的方式,本来这种方式可以有效的降低搜索的时间,但是因为这一题比较特殊(集合比较多)所以递归时间并没有减少很多,另外大家合并的时候一定要检查是不是同一个集合,不然会出错,并且MLE

  另外这题,真是尼玛,有BUG,只能交单次数据(也就是不能while(~scanf())),真是个脑残bug技术分享

  

  

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 typedef int Position;
 6 
 7 Position Find(Position);
 8 void Union_Set(Position, Position);
 9 int If_Same_Set(Position, Position);
10 
11 static int *Set = NULL;
12 
13 int main(void)
14 {
15     int N, case_sum, i;
16     int ans = 0, inform, x, y;
17     scanf("%d%d", &N, &case_sum);
18     Set = new int[3 * (N + 1)];
19     for (i = 1; i <= 3 * N; i++) Set[i] = -1;
20     for (i = 0; i < case_sum; i++)
21     {
22         scanf("%d%d%d", &inform, &x, &y);
23         if (x > N || y > N)//如果在区域外,直接判断出错
24         {
25             ans++;
26             continue;
27         }
28         else if (inform == 1)
29         {
30             if (If_Same_Set(x, y + N) || If_Same_Set(x, y + 2 * N))
31                 //如果已经是捕食集合中,出错
32                 ans++;
33             else//否则,则把xy的三个属性分别合并
34             {
35                 Union_Set(x, y);
36                 Union_Set(x + N, y + N);
37                 Union_Set(x + 2 * N, y + 2 * N);
38             }
39         }
40         else if (inform == 2)
41         {
42             if (If_Same_Set(x, y) || If_Same_Set(x, y + 2 * N))
43                 //如果已经在非捕食集或已统一集合,出错
44                 ans++;
45             else
46             {
47                 Union_Set(x, y + N);
48                 Union_Set(x + N, y + 2 * N);
49                 Union_Set(x + 2 * N, y);
50             }
51         }
52     }
53     printf("%d\n", ans);
54     delete Set;
55     return 0;
56 }
57 
58 Position Find(Position x)
59 {
60     //路径压缩
61     if (Set[x] < 0)
62         return x;
63     else
64         return Set[x] = Find(Set[x]);
65 }
66 
67 int If_Same_Set(Position x, Position y)
68 {
69     return  Find(x) == Find(y);
70 }
71 
72 void Union_Set(Position x, Position y)
73 {
74     Position Rootx, Rooty;
75     Rootx = Find(x);
76     Rooty = Find(y);
77 
78     if (Rootx != Rooty)//按大小求并,千万要注意不能是同一个集合的合并,不然会MLE
79     {
80         if (Set[Rootx] < Set[Rooty])
81         {
82             Set[Rootx] += Set[Rooty];
83             Set[Rooty] = Rootx;
84         }
85         else
86         {
87             Set[Rooty] += Set[Rootx];
88             Set[Rootx] = Rooty;
89         }
90     }
91 }

 

  

DisJSet:食物链(POJ 1182)

原文:http://www.cnblogs.com/Philip-Tell-Truth/p/4850887.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!