Codevs1074食物鍊

http://codevs.cn/problem/1074/

權重并查集/擴充域并查集的經典題目

方案一：權重并查集

思路

我們設rank[i]記錄記錄i到其father的關系（或言距離）,有0,1,2三種表示同類,吃與被吃 ，然後注意在路徑壓縮時維護此關系，當新得到的兩隻動物的關系已經被确定是判斷此時關系是否沖突，合并時确定新增關系（u與v）。

一定要注意：食物鍊為環狀結構。

在這裡解釋兩處對合并的關鍵性處理的代碼，也是本題的難點所在：

第一處：

1.若y與v同類: (1) x與u同類,則u與v同類 = 0 (2) x吃u,則v吃u,u被v吃 = 2 (3) x被u吃,則v被u吃,u吃v = 1

2.若y吃v: (1) x與u同類,則y與u同類,u吃v = 1 (2) x吃u,則y吃u,u與v同類 = 0 (3) x被u吃,則y被u吃,v吃u,u被v吃 = 2

3.若y被v吃： (1) x與u同類,則y與u同類,u被v吃 = 2 (2) x吃u,則y吃u,u吃v = 1 (3) x被u吃,則y被u吃,u與v同類 = 0

第二處

1.若y與v同類： (1) x與u同類,則x吃v,u吃v = 1 (2) x吃u,則x吃v,u與v同類 = 0 (3) x被u吃,則y吃u,v吃u,u被v吃 = 2

2.若y吃v： (1) x與u同類,則v吃u,u被v吃 = 2 (2) x吃u,則y與u同類,u吃v = 1 (3) x被u吃,則y吃u,y與v同類 = 0

3.若y被v吃： (1) x與u同類,v吃y,則x與v同類,u與v同類 = 0 (2) x吃u,則y與u同類,u被v吃 = 2 (3) x被u吃,則y吃u,u吃v = 1

在這裡我們是分情況讨論證明算法的合理性，還有一種向量法證明具體請見：http://www.studyai.com/article/0d732f3e 但要注意，向量法的解釋方法，适用情況比較少，僅适用于不超過三種關系的情況。

代碼

//權重并查集
#include<iostream>//注意僅有三種動物 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,k,p,x,y,ans;
int fa[],rank[];
int find(int x)
{
    if(fa[x]==x)
    return fa[x]; 
    int tmp=fa[x];
    fa[x]=find(fa[x]);
    rank[x]=(rank[tmp]+rank[x])%;//路徑壓縮,目前與根節點的關系(距離) = 沿路關系相加  
    return fa[x];                 //當作記錄原來到根節點的距離了解好啦~ 
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=;i<=n;i++)
    fa[i]=i;
    for(int i=;i<=k;i++)
    {
        scanf("%d %d %d\n",&p,&x,&y);
        if(x>n||y>n)
        {
            ans++;
            continue;
        }
        int u=find(x);
        int v=find(y);
        if(p==)//x與y同類 
        {
            if(u==v)
            {
                if(rank[x]!=rank[y])//同類則關系相同,隻維護與其父親的關系 
                ans++;
            }
            else
            {
                fa[u]=v;
                rank[u]=(rank[y]-rank[x]+)%;//注意此時的u,v,x,y不一定包含3種動物 
            }//+3為了調整關系(僅三種)            //第一處          
        }                                     
        if(p==)//x吃y                         
        {                                       
            if(u==v)
            {
                if(rank[x]!=(rank[y]+)%)//需滿足條件//若x與fa同類,則y被fa吃 
                ans++;                                //若x吃fa,則y與fa同類 
            }                                         //若x被fa吃,則y吃fa
            else                                      //-----環狀結構！ 
            {
                fa[u]=v;
                rank[u]=(rank[y]-rank[x]+)%;//第二處
            }                                 
        }                                      
    }
    printf("%d",ans);
    return ;
}
           

對于本題的權重并查集的做法，總而言之了解起來還是很有難度的，而且是仁者見仁智者見智，但在進行一定的了解後如果遇到新題，會發現解題方法其實是差不多的。

根據不同的題目推導路徑壓縮，判斷以及合并的操作方法，如有必要就分情況讨論一下，還是可以為算法設計提供很不錯的思路的。

方案二：擴充域并查集

注意：對于本題，所謂并查集拆點（将一個點拆成三個）的做法與擴充域并查集其實就是從兩個方面解釋算法而已，并無實質差别。

思路

開三倍的fa[i]，分别表示i的同類域，i的吃域，i的被吃域。然後根據描述依次加入并查集，結合題設條件判斷沖突即可。

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,k,p,x,y,ans;
int x_1,y_1,x_2,y_2,x_3,y_3;//include-cmath...不能使用y1 
int fa[];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);//随意路徑壓縮 
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=;i<=*n+;i++)
    fa[i]=i;
    for(int i=;i<=k;i++)
    {
        scanf("%d%d%d",&p,&x,&y);
        if(x>n||y>n)
        {
            ans++;
            continue;
        }
        x_1=find(x);//同類域 
        y_1=find(y);
        x_2=find(x+n);//吃域 
        y_2=find(y+n);
        x_3=find(x+n*);//被吃域 
        y_3=find(y+n*);
        if(p==)
        {
            if(x_1==y_2||x_2==y_1)//y吃x或者x吃y 
            ans++;
            else
            {
                fa[x_1]=y_1;//x與y同類 
                fa[x_2]=y_2;//x的吃域即y的吃域 
                fa[x_3]=y_3;//x的敵人即y的敵人 
            }
        }
        if(p==)
        {
            if(x_1==y_1||x_1==y_2)//x與y同類或y吃x 
            ans++;
            else
            {
                fa[y_1]=x_2;//x吃y 
                fa[y_2]=x_3;//y的食物吃x---長度為3的環狀結構 
                fa[y_3]=x_1;//x的同類吃y 
            } 
        }
    }
    printf("%d",ans);
    return ;
}
           

本題的擴充域并查集做法還是比較容易了解的。