洛谷2024 [NOI2001]食物链

Luogu

算法

建立三个并查集,分别代表A、B、C。

对于操作1,在每一个并查集中将这两个动物合并。

对于操作2,即 $x$ 吃 $y$,那么把 A 中的 $x$ 和 B 中的 $y$ 合并、把 B 中的 $x$ 和 C 中的 $y$ 合并,把 C 中的 $x$ 和 A 中的 $y$ 合并。

判断就很简单了。如果 A 吃 B 或者 B 吃 A ,那它们就不是同类;如果 A 和 B 是同类或者 B 吃 A,那么 A 就不吃 B。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int root[50000*3+10];
inline int find(int u) {
    if (root[u]!=u) root[u]=find(root[u]);
    return root[u];
}
inline void merge(int u,int v) {
    u=find(u),v=find(v);
    if (u!=v) root[u]=v;
}

int main() {
    int n,k,ans=0;
    n=read(),k=read();
    for (re int i=1;i<=n*3;i++) root[i]=i;
    for (re int i=1;i<=k;i++) {
        int op,X,Y; op=read(),X=read(),Y=read();
        if (X>n||Y>n) { ans++; continue; }
        if (op==1) {
            if (find(X)==find(Y+n)||find(X+n)==find(Y)) ans++;
            else { merge(X,Y); merge(X+n,Y+n); merge(X+n+n,Y+n+n); }
        }
        else if (op==2) {
            if (find(X)==find(Y)||find(X+n)==find(Y)) ans++;
            else { merge(X,Y+n); merge(X+n,Y+n+n); merge(X+n+n,Y); }
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 10 月 17 日 09 : 08 AM

发表评论