程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 又見關系並查集以POJ 1182 食物鏈為例

又見關系並查集以POJ 1182 食物鏈為例

編輯：C++入門知識

又見關系並查集以POJ 1182 食物鏈為例

簡單的關系並查集一般很容易根據給出的關系搞出一個有向的環，那麼兩者之間的關系就變成了兩者之間的距離。

對於此題：

若u，v不在一個集合內，則顯然此條語句會合法（暫且忽略後兩條，下同）。

那麼將fu 變為 fv的兒子時需加一條權值為 w 的邊，w 滿足(w + ru)%3 = (rv+ (D == 1? 0 : 1))%3（ru，rv分別為u，v與fv的關系，即距離）。

之所以在D == 2時加 1，是因為u吃v表明著u到fv的距離比v到fv的距離大1。

同理，D == 1時，表明兩者到fv的距離應該相等。

若u，v在一個集合內，只需要判斷ru%3 == (rv+(D == 1?):1))%3 是否成立即可。

不過這個題數據略坑啊，寫成多組輸入的根本過不了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f

using namespace std;

struct N
{
    int fa,re;
} st[50010];

int Find(int x,int &R)
{
    int f,re = 0;

    f = x;

    while(f != st[f].fa)
    {
        re = (re+st[f].re)%3;
        f = st[f].fa;
    }

    R = re;
    int tre = 0,temp,tf;

    while(x != st[x].fa)
    {
        tf = st[x].fa;
        temp = st[x].re;
        
        st[x].re = (re-tre+3)%3;

        tre = (tre+temp)%3;
        st[x].fa = f;
        x = tf;
    }

    return f;
}

bool Merge(int w,int u,int v)
{
    int ru,rv;
    int fu = Find(u,ru);
    int fv = Find(v,rv);

    if(fu != fv)
    {
        st[fu].fa = fv;
        if(w == 2)
            st[fu].re = ((rv+1)%3 - ru + 3)%3;
        else
            st[fu].re = (rv%3- ru + 3)%3;
    }
    else
    {
        if(w == 1 && ru != rv)
            return false;

        if(w == 2 && ru != (rv+1)%3 )
            return false;
    }

    return true;
}

int main()
{
    int n,k;

    int i,j,u,v,w;

    scanf("%d %d",&n,&k);
    {
        for(i = 1; i <= n; ++i)
            st[i].fa = i,st[i].re = 0;

        int ans = 0;

        while(k--)
        {
            scanf("%d %d %d",&w,&u,&v);

            if(u > n || v > n || (w == 2 && u == v))
            {
                ans++;
                continue;
            }

            if(Merge(w,u,v) == false)
            {
                ans++;
            }
        }

        printf("%d\n",ans);
    }

    return 0;
}