食物链

POJ-1182

一个很好的分析博客：https://blog.csdn.net/niushuai666/article/details/6981689

三种关系：两者同类，吃父节点，被父节点吃，所以权值可以用0，1，2表示

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<algorithm>

#include<cmath>

#include<vector>

#include<map>

using namespace std;

const int maxn=50004;

int n,m;

int set[maxn];

int sum[maxn];

int ans;

int find(int x){

    if(x==set[x])

        return set[x];

    else{

        int parent=set[x];

        set[x]=find(set[x]);

        sum[x]=(sum[x]+sum[parent])%3;

        return set[x];

    }

}

void merge(int type,int a,int b){

    int ta=find(a);

    int tb=find(b);

    if(ta==tb){

        if((sum[a]-sum[b]+3)%3!=type-1)

         ans++;

    }else{

        set[ta]=tb;

        sum[ta]=(sum[b]-sum[a]+type-1+3)%3;

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=0;i<=n;i++){

        sum[i]=0;

        set[i]=i;

    }

    int d,a,b;

    for(int i=0;i<m;i++){

        scanf("%d%d%d",&d,&a,&b);

        if(a>n||b>n){

            ans++;

            continue;

        }else if(a==b&&d==2){

            ans++;

            continue;

        }else merge(d,a,b);

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

POJ-1182(经典带权并查集)

食物链

POJ-1182

一个很好的分析博客：https://blog.csdn.net/niushuai666/article/details/6981689

最新文章

热门文章