2016年2月16日 星期二

[POJ 1182]食物链

可以看出,我們永遠不會知道特定的某隻動物是$A$、$B$或$C$

為了方便說明,令$S_{i}$為第$i$隻動物

因此,我們只能對於$S_{i}$做出$S_{i}=A$、$S_{i}=B$或者$S_{i}=C$假設
當某個假設可以推到另一個假設,我們就將這兩個假設連邊,剛好在這題,如果$A$可以推到$B$,那麼$B$也可以推到$A$,因此可以直接連無向邊
再仔細想想,可以知道如果$X$吃$X$的情況出現,若且唯若可以從$S_{i}=A$的假設推到$S_{i}\neq A$的假設,也就是這兩個假設在同一個連通塊裡面

我們只要判斷連通性就好了,可以用並查集來維護!

如果上面的題解仔細看了好幾遍還是沒有頭緒,請參考code

時間複雜度:$O(K\alpha(N))$ (不過code裡面的並查集是$O(\log N)$)

p.s. POJ的測資結尾竟然還有其他數字!所以如果你是做重複輸入的,會莫名地得到WA,需要在code裡面加上那個break才能通過Orz

code:
#include<cstdio>
#include<cassert>
using namespace std;
//void assert(bool valid){if(valid)return;for(int a=0,b=0;;)a/=b;}
struct Djset
{
    int s[150000];
    void clear(const int n){for(int i=0;i<n;i++)s[i]=i;}
    int find(const int a){return s[a]==a?a:(s[a]=find(s[a]));}
    bool merge(int a,int b){if((a=find(a))==(b=find(b)))return false;s[a]=b;return true;}
    int operator[](const int i){return find(i);}
}DJ;
int N,K;
int main()
{
    while(scanf("%d%d",&N,&K)==2)
    {
        DJ.clear(N*3);
        int ans=0;
        for(int i=0,d,a,b;i<K;i++)
        {
            scanf("%d%d%d",&d,&a,&b),a--,b--;
            assert(a>=0&&b>=0);
            if(a>=N||b>=N)ans++;
            else if(d==1)
            {
                if(DJ[a]==DJ[N+b]||DJ[a]==DJ[N+N+b])ans++;
                else for(int j=0;j<3;j++)DJ.merge(N*j+a,N*j+b);
            }
            else if(d==2)
            {
                if(DJ[a]==DJ[b]||DJ[a]==DJ[N+N+b])ans++;
                else for(int j=0;j<3;j++)DJ.merge(N*j+a,N*((j+1)%3)+b);
            }
            else assert(0);
        }
        printf("%d\n",ans);
        break;
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原