poj 1182 食物链(转) - wxdlut的日志 - 网易博客

poj 1182 食物链(转)

POJ 题解 2009-09-27 17:43:11 阅读516 评论2 字号：大中小

题目描述：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

建议：做此题之前先做 poj 2524 和 poj 1611。这两道题都是并查集的基础应用。
关键词：并查集 相对关系
思路： （用一个并查集就够了，同时对每个节点保持其到根结点的相对类别偏移量）
     1.p[x]表示x的根结点。r[x]表示p[x]与x的关系。r[x] == 0 表示p[x]与x同类；1表示p[x]吃x；2表示x吃p[x]。

     2.怎样划分一个集合呢？
        注意，这里不是根据x与p[x]是否是同类来划分。而是根据“x与p[x]能否确定两者之间的关系”来划分，若能确定x与p[x]的关系，则 它们同属一个集合。

     3.怎样判断一句话是不是假话？
        假设已读入 D , X , Y , 先利用find_set()函数得到X , Y 所在集合的代表元素 rx , ry ,若它们在同一集合（即 rx == ry ）则可以判断这句话的真伪（ 据 2. ）.
        若 D == 1 而 r[X] != r[Y] 则此话为假。（D == 1 表示X与Y为同类，而从r[X] != r[Y]可以推出 X 与 Y 不同类。矛盾。）
        若 D == 2 而 r[X] == r[Y] （X 与Y为同类）或者　r[X] == ( r[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.其他注意事项:
        在union_set( rx , ry )过程中若将S(ry)合并到S(rx)上，则相应的r[ry]必须更新为ry相对于rx的关系。怎样得到更新关系式？
     //以下来自poj 1182 中的Discuss
         用向量运算。
         现在已知关系: rx与x, ry与y, x与y，现在求rx与ry的关系。学过向量应该能做出来吧。。。
     在find_set( x )过程中要更新所有从x到rx路径上的结点与代表元素的相对关系。原因将在6中说明。
  
 6.code + comment:
//===================================================================================

#include <iostream>
using namespace std;

void make_set( int [] , int [] , int );
int find_set( int [] , int [] , int );
void union_set( int [] , int [] , int , int , int , int , int );

int main()
{
     int p[50001];
     int r[50001];
     int n, k;
     int d, x, y, rx, ry;
     int fs;
 
     scanf( "%d%d" , &n , &k );
     make_set( p , r , n );
     fs = 0;
     while ( k-- > 0 )
     {
           scanf( "%d%d%d" , &d , &x , &y );
           if ( x > n || y > n || ( d == 2 && x == y ) )
           {
                fs++;
                continue;
           }
           rx = find_set( p , r , x );
           ry = find_set( p , r , y );
           if ( rx == ry )    //可以确定X与Y的关系，也就可以判断此话的真伪。
                if ( d == 1 && r[x] != r[y] )
                     fs++;
                else
                {
                     if ( d== 2 && r[x] != ( r[y] + 2 ) % 3 )
                          fs++;
                }
           else
                union_set( p , r , rx , ry , x , y , d );
   }

   cout << fs << endl;

   return 0;
}

void make_set( int p[] , int r[] , int n )
{
     for ( int i = 0 ; i <= n ; i++ )
     {
          p[i] = i;
          r[i] = 0;
     }
}

int find_set( int p[] , int r[] , int x )
{
      if ( p[x] == x ) return x;

      int temp_px = p[x];    
      p[x] = find_set( p , r , p[x] );  //递归寻找元素x所在集合的代表元素 rx
      r[x] = ( r[temp_px] + r[x] ) % 3;  //important. 更新r[]数组中x与代表元素的相对关系。更新原因:代表元素在
                                                     //union_set操作中被改变了。至于这个式子的推得.可以枚举rx与p[x], p[x]
                                                     //与x的关系，然后观察得到。更好的方法是向量运算。来自poj 1182 Discuss
      return p[x];
}

void union_set( int p[] , int r[] , int rx , int ry , int x , int y , int d )
{
      p[ry] = rx;
      r[ry] = ( r[x] - r[y] + 2 + d ) % 3;    //同上。这两个关系的推得实际上是这道题的关键所在。
}

//===================================================================================
          
 7.coding过程中的一些细节
 　并查集的操作中有一个 启发式合并。即用一个启发函数rank[]，每次合并两个集合时总是将元素个数少的合并到元素个数多的集合上。但经过测试，在此题中并没有明显的优化效 果。
 　关于find_set()的递归与非递归实现：
 　一开始时我用的是非递归：代码如下：
//===================================================================================

int find_set( int p[] , int r[] , int x )
{
     int rx = x;
     int temp_px;

     while ( p[rx] != rx ) rx = p[rx];
     while ( x != rx )
     {
          temp_px = p[x];
          r[x] = ( r[p[x] + r[x] ) % 3;
          p[x] = rx;
          x = temp_px;
     }

     return rx;
}

//===================================================================================
   但是反复WA ...参考别人的源程序。我改成了上面的递归实现。然后AC了。比较这两段代码，功能几乎是一样的啊，问题出在哪呢？原来非递归中计算r[]的顺序是先计 算r[x]再计算r[p[x]]，而递归中是先计算r[p[x]]再计算r[x]。显然后者是正确的。因为必须先更新p[x]与新的代表元素的相对关系再 更新r[x]才有意义。否则，根据非递归计算的r[x]永远只是x相对于未更新之前的代表元素的相对关系。
 　我很郁闷。我一定要写成 非递归的！好吧。用栈实现吧。于是有了下面的code:

//===================================================================================

int find_set( int p[] , int r[] , int x )
{

      int rx = x;
      int stack[45];
      int t = 0;

      while ( p[rx] != rx )
      {
            stack[t++] = rx;
            rx = p[rx];
      }
      stack[t] = rx;

      while ( t >= 0 )
      {
            r[stack[t]] = ( r[p[stack[t]]] + r[stack[t]] ) % 3;
            p[stack[t]] = rx;
            t--;
       }

       return rx;

}

//===================================================================================
   经过测试。。。非递归比递归慢。。。。。泪。。。
 
 8.over.

另：
虽然已经过了好 多的人了，但是感觉今天学到的思路太经典了，感谢alpc50大牛，使得我对并查集的应用又前进了一步～～～
首先建议来看本文的ACMer们去做做poj1988，思路同本文类似的说～～～
刚拿到这道题，我的想法很单纯：开三个并查集，分别保存同类、食物、天敌，然后每次归并都分别判断处理。这样的好处是直接，坏处是非常的繁琐。
经alpc50大牛提点，我才认识到只需要一个并查集就够了，同时对每个节点保持其到根结点的相对类别偏移量，定义为：
0 ——同类；
1——食物；
2——天敌。
这样，在每次并查集压缩路径操作中更新该值即可。
下面是核心代码：
int finds(int k)
{
if (p[k]==k)
   return k;
int t=finds(p[k]);
ch[k]=(ch[k]+ch[p[k]])%3;
p[k]=t;
return t;
}

void check(int x,int y,int d)
{
int tp=finds(x),tq=finds(y);
if (tp==tq)
{
   if ((ch[y]-ch[x]+3)%3!=d)
    ++lyn;
   return;
}
p[tp]=tq;
ch[tp]=(ch[y]-ch[x]-d+6)%3;
}