poj 1182 食物鏈(轉(zhuǎn))

POJ 題解 2009-09-27 17:43:11 閱讀516 評論2 字號：大中小

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

建議：做此題之前先做 poj 2524 和 poj 1611。這兩道題都是并查集的基礎(chǔ)應(yīng)用。
關(guān)鍵詞：并查集 相對關(guān)系
思路： （用一個(gè)并查集就夠了，同時(shí)對每個(gè)節(jié)點(diǎn)保持其到根結(jié)點(diǎn)的相對類別偏移量）
     1.p[x]表示x的根結(jié)點(diǎn)。r[x]表示p[x]與x的關(guān)系。r[x] == 0 表示p[x]與x同類；1表示p[x]吃x；2表示x吃p[x]。

     2.怎樣劃分一個(gè)集合呢？
        注意，這里不是根據(jù)x與p[x]是否是同類來劃分。而是根據(jù)“x與p[x]能否確定兩者之間的關(guān)系”來劃分，若能確定x與p[x]的關(guān)系，則 它們同屬一個(gè)集合。

     3.怎樣判斷一句話是不是假話？
        假設(shè)已讀入 D , X , Y , 先利用find_set()函數(shù)得到X , Y 所在集合的代表元素 rx , ry ,若它們在同一集合（即 rx == ry ）則可以判斷這句話的真?zhèn)危?據(jù) 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.上個(gè)問題中 r[X] == ( r[Y] + 1 ) % 3這個(gè)式子怎樣推來？
        假設(shè)有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;
        事實(shí)上，對于上個(gè)問題有更一般的判斷方法：
           若 ( r[Y] - r[X] + 3 ) % 3 != D - 1 ，則此話為假。（來自poj 1182中的Discuss ）

     5.其他注意事項(xiàng):
        在union_set( rx , ry )過程中若將S(ry)合并到S(rx)上，則相應(yīng)的r[ry]必須更新為ry相對于rx的關(guān)系。怎樣得到更新關(guān)系式？
     //以下來自poj 1182 中的Discuss
         用向量運(yùn)算。
         現(xiàn)在已知關(guān)系: rx與x, ry與y, x與y，現(xiàn)在求rx與ry的關(guān)系。學(xué)過向量應(yīng)該能做出來吧。。。
     在find_set( x )過程中要更新所有從x到rx路徑上的結(jié)點(diǎn)與代表元素的相對關(guān)系。原因?qū)⒃?中說明。
  
 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的關(guān)系，也就可以判斷此話的真?zhèn)巍?br>                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[]數(shù)組中x與代表元素的相對關(guān)系。更新原因:代表元素在
                                                     //union_set操作中被改變了。至于這個(gè)式子的推得.可以枚舉rx與p[x], p[x]
                                                     //與x的關(guān)系，然后觀察得到。更好的方法是向量運(yùn)算。來自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;    //同上。這兩個(gè)關(guān)系的推得實(shí)際上是這道題的關(guān)鍵所在。
}

//===================================================================================
          
 7.coding過程中的一些細(xì)節(jié)
 　并查集的操作中有一個(gè) 啟發(fā)式合并。即用一個(gè)啟發(fā)函數(shù)rank[]，每次合并兩個(gè)集合時(shí)總是將元素個(gè)數(shù)少的合并到元素個(gè)數(shù)多的集合上。但經(jīng)過測試，在此題中并沒有明顯的優(yōu)化效 果。
 　關(guān)于find_set()的遞歸與非遞歸實(shí)現(xiàn)：
 　一開始時(shí)我用的是非遞歸：代碼如下：
//===================================================================================

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;
}

//===================================================================================
   但是反復(fù)WA ...參考別人的源程序。我改成了上面的遞歸實(shí)現(xiàn)。然后AC了。比較這兩段代碼，功能幾乎是一樣的啊，問題出在哪呢？原來非遞歸中計(jì)算r[]的順序是先計(jì) 算r[x]再計(jì)算r[p[x]]，而遞歸中是先計(jì)算r[p[x]]再計(jì)算r[x]。顯然后者是正確的。因?yàn)楸仨毾雀聀[x]與新的代表元素的相對關(guān)系再 更新r[x]才有意義。否則，根據(jù)非遞歸計(jì)算的r[x]永遠(yuǎn)只是x相對于未更新之前的代表元素的相對關(guān)系。
 　我很郁悶。我一定要寫成 非遞歸的！好吧。用棧實(shí)現(xiàn)吧。于是有了下面的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;

}

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;
}