食物链 – POJ1182

题意:A国有3个物种,A捕食B,B捕食C,C捕食A.某人对A国的n个动物发表评价,内容如下:
1 x y : x和y是一个物种
2 x y : x捕食y
如果这个人的某个评论与前文的真话出现矛盾或x,y>n,这个评论成为假话,反之成为真话.
求他说了多少假话.


分析:由于捕食关系成环,如果我们发现了一条食物链A->B->C->D->E->F…,那么一定有A=D,B=E,C=F,以此类推.也就是说食物链上每3个动物都是不同的,隔着两个的动物是相同的.(显然),因此我们可以记录每只动物距所在食物链最前端的距离.这个就可以使用并查集完成.
如果我们发现了这样的两条食物链:
A->B
D->E
且某人说B和E是同一个物种,按照定义,这是句真话.因此我们需要将两个食物链合并.
合并连边A->D,为了保证B和E仍然是一个物种,D距离A的距离应该设为0.保证了食物链的合法性.

补充:网络上普遍的做法是保存节点与父节点的吃与被吃的关系,但这种关系不好想,也不容易推广到物种更多的食物链上去.这篇博客的做法,我自认为是基于同余的easy but effective的做法.


#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 50001

using namespace std;

int fa[MX],sp[MX],n,k;

int findfa(int x)
{
    if(x==fa[x])return x;
    else
    {
        findfa(fa[x]);
        sp[x]+=sp[fa[x]];
        fa[x]=fa[fa[x]];
        return fa[x];
    }
}

inline int same(int a,int b)
{
    int f1=findfa(a),f2=findfa(b);
    if(f1==f2)
    {
        if(sp[a]%3==sp[b]%3)return 0;
        else return 1;
    }
    else
    {
        fa[f1]=f2;
        sp[f1]=(sp[b]-sp[a])%3+3;
        return 0;
    }
}

inline int eat(int a,int food)
{
    int f1=findfa(a),f2=findfa(food);
    if(f1==f2)
    {
        if(sp[a]%3==(sp[food]+1)%3)return 0;
        else return 1;
    }
    else
    {
        fa[f1]=f2;
        sp[f1]=(sp[food]-sp[a])%3+4;
        return 0;
    }
}

int main()
{
    int a,b,c,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++)fa[i]=i;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(b>n||c>n)ans++;
        else if(a==1)ans+=same(b,c);
        else ans+=eat(b,c);
    }
    printf("%d\n",ans);
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *