poj1182 食物链（带权并查集）

题目链接

思路

前面做的带权并查集的权值记录该结点与其父结点是否是同一类，只有两种取值情况（0,1），在这题中某结点a和其父结点b的取值共有三种情况：a和b同类；a被b吃；a吃b，对应三种情况，r[a]的取值分别为0,1,2。这题的难点是递推公式，路径压缩递推公式为r[x] = (r[x] + r[t]) % 3，合并集合递推公式为r[ra] = (3 - r[a] + d - 1 + r[b]) % 3，递推公式形式的推导可以参考这篇文章。

代码

 #include <cstdio>

 const int N =  + ;

 int p[N];

 int r[N];

 void make_set(int n)

 {

     for (int i = ;i <= n;i++)

     {

         p[i] = -;

         r[i] = ;

     }

 }

 int find_root(int x)

 {

     if (p[x] == -)

         return x;

     int t = p[x];

     p[x] = find_root(p[x]);

     r[x] = (r[x] + r[t]) % ;    //路径压缩递推公式

     return p[x];

 }

 int union_set(int d, int a, int b)

 {

     int ra = find_root(a);

     int rb = find_root(b);

     if (ra != rb)    //a,b不在同一集合，合并

     {

         p[ra] = rb;

         r[ra] = ( - r[a] + d -  + r[b]) % ;    //合并集合递推公式

         return ;

     }

     else

     {

         if ((r[a] +  - r[b]) %  != d - )

             return ;

         else return ;

     }

     return ;

 }

 int main()

 {

     //freopen("poj1182.txt", "r", stdin);

     int n, k;

     scanf("%d%d", &n, &k);

     make_set(n);

     int d, x, y;

     int ans = ;

     for (int i = ; i < k;i++)

     {

         scanf("%d%d%d", &d, &x, &y);

         if (x > n || y > n || (d ==  && x == y))

             ans++;

         else ans+=union_set(d, x, y);

     }

     printf("%d\n", ans);

     return ;

 }

参考：

1、http://www.voidcn.com/article/p-mwvpmony-qx.html

2、https://www.cnblogs.com/zhuanzhuruyi/p/5863738.html

巴特西

poj1182 食物链（带权并查集）

最新文章

热门文章