题解 P2024 [NOI2001]食物链

· · 个人记录

法一： 开三倍数组，并查集维护三个物种关系即可，详见注解

#include<bits/stdc++.h>

using namespace std;
const int maxn=5e4+5;
int fa[maxn*3],n,k,type,x,y,ans;
int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - 48, ch = getchar();
    return x * f;
}
int find(int x) {
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
int main() {
    n=read(),k=read();
    for(int i=1; i<=3*n; i++) fa[i]=i;
    /*
    分为1-n，n+1-2n,2n+1-2n三个集合，分别表示A,B,C三物种
   对任意元素x，通过x确定x的同类，x+n确定x的猎物,x+2n确定x的天敌
   由题意若x，y是同类，则分别合并x和y，x+n和y+n，x+2n和y+2n
    表示xy是同类，x的天敌是y的天敌，x的猎物是y的猎物
    若x吃y，则合并x和y+n，x+n和y+2n，x+2n和y
    表示x吃y，x的猎物吃y的猎物，x的猎物的猎物吃y的猎物的猎物   
    */
    for(int i=1; i<=k; i++) {
        type=read(),x=read(),y=read();
        if(x>n||y>n) ans++;
        else {
            if(type==1) {
                if(find(x+n)==find(y)||find(x+2*n)==find(y)) ans++;
                //||后面第二个条件写成find(x)==find(y+n)也行
                //y吃x，或者x吃y，则不是同类 
                else {
                    fa[find(x)]=find(y);
                    fa[find(x+n)]=find(y+n);
                    fa[find(x+2*n)]=find(y+2*n);
                }
            } else {
                if(find(x)==find(y)||find(x+n)==find(y)) ans++;
                //x和y是同类，或者 y吃x，则与x吃y矛盾 
                else {
                    fa[find(x)]=find(y+n); 
                    fa[find(x+n)]=find(y+2*n);
                    fa[find(x+2*n)]=find(y);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

法二：

带权并查集处理：

参考博客：

https://blog.csdn.net/qq_39520417/article/details/81569982 https://blog.csdn.net/niushuai666/article/details/6981689

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
int fa[maxn],n,k,type,x,y,ans,dis[maxn];
int find(int x) {
    if(fa[x]!=x) {
        int now=fa[x];
        fa[x]=find(fa[x]);
        (dis[x]+=dis[now])%=3;
    }
    return fa[x];
}
int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - 48, ch = getchar();
    return x * f;
}
int main() {
    n=read(),k=read();
    for(int i=1; i<=n; i++) fa[i]=i,dis[i]=0;
    for(int i=1; i<=k; i++) {
        type=read(),x=read(),y=read();
        if((x>n||y>n)||(type==2&&x==y)) ans++;
        else if(find(x)==find(y)) {
            if(type==1&&dis[x]!=dis[y]) ans++;
            if(type==2&&(dis[x]+1)%3!=dis[y]) ans++;
        } else {
            int p=find(x),q=find(y);
            fa[q]=p;
            dis[q]=(dis[x]-dis[y]+type-1+3)%3;
        }
    }
    cout<<ans;
    return 0;
}

类似题目：

SP3377 BUGLIFE - A Bug’s Life

P1892 团伙

UVA1329 Corporative Network

需要注意的是，团伙中没有说朋友的敌人是敌人，所以合并时不能将p+n和q+n一起合并，否则意味着p与q是朋友，且p的敌人是q的敌人的朋友，这在题意中未体现