程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1182 食物鏈 (種類並查集)

poj 1182 食物鏈 (種類並查集)

編輯：C++入門知識

食物鏈 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 41805 Accepted: 12160

Description

動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B， B吃C，C吃A。
現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們並不知道它到底是哪一種。
有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：
第一種說法是"1 X Y"，表示X和Y是同類。
第二種說法是"2 X Y"，表示X吃Y。
此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。
1）當前的話與前面的某些真的話沖突，就是假話；
2）當前的話中X或Y比N大，就是假話；
3）當前的話表示X吃X，就是假話。
你的任務是根據給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000），輸出假話的總數。

Input

第一行是兩個整數N和K，以一個空格分隔。
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。

Output

只有一個整數，表示假話的數目。

Sample Input

Sample Output

Source

Noi 01

思路來源於、詳細題解見飄過的小牛

思路：

並查集，維護一個pre-根節點數組和一個rel-根節點到該點的關系（偏移量）數組。rel只有三種取值0、1、2；0表示同種關系，1表示根節點吃該節點，2表示根節點被該節點吃。

輸入op、x、y時，fx=Find（x），fy=Find（y）；如果fx！=fy，那麼將fx集合和fy集合合並，pre[fy]=fx；fx->fy=fx->x+x->y+y->fy；x-y為op-1，即rel[fy]=(rel[x]+op-1-rel[y]+3)%3;如果fx=fy，那麼需檢驗是否產生沖突，x->y=x->fx+fx->y，即檢驗(-rel[x]+rel[y]+3)%3是否與op-1相等即可。

查找的時候更新每個點的rel數組，根據以前的rel以及現在的它的父親的rel更新，rel[x]=(rel[px]+rel[x])%3;

ps：這題很坑，要單組數據才行，多組要WA。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 50005
#define MAXN 100005
#define OO (1<<31)-1
#define mod 90003
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,tot,flag,cnt;
int pre[maxn],rel[maxn];

int Find(int x)
{
    if(x==pre[x]) return x;
    int tmp=pre[x];
    pre[x]=Find(pre[x]);
    rel[x]=(rel[tmp]+rel[x])%3;
    return pre[x];
}
bool Merge(int op,int x,int y)
{
    int fx=Find(x),fy=Find(y);
    if(fx==fy) // 在相同集合 判斷是否沖突
    {
        if((-rel[x]+rel[y]+3)%3!=op-1) return true ;
    }
    else // 合並
    {
        pre[fy]=fx;
        rel[fy]=(rel[x]+op-1-rel[y]+3)%3;
    }
    return false ;
}
int main()
{
    int i,j,t,op,x,y;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++) pre[i]=i,rel[i]=0;
    ans=0;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(x>n||y>n||op==2&&x==y)
        {
            ans++;
            continue ;
        }
        if(Merge(op,x,y)) ans++;
    }
    printf("%d\n",ans);
    return 0;
}