link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=357#problem/A
这题已经不能用经典来形容了。。一开始看的时候一点想法都没有,后来实在忍不住去搜解题报告。。
结果什么向量法的看都看不懂,真心弱菜了~~给答案都不会抄。。。后来想到根据D题的想法思路发现
也可以实现,通过构造食物链中的三个元素,进行讨论合并~~~
代码上有注释;
code:

/*构造食物链,i代表同类,i+n代表i+n吃i,i+2*n代表i+2*n被i吃*/
#include <iostream>
#include <cstdio>
#define N 50010
using namespace std;
int a[N*3];

void init()
{
    int i;
    for(i=1;i<N*3;i++)
        a[i]=i;
}

int find(int x)
{
    if(x!=a[x])
        a[x]=find(a[x]);
    return a[x];
}

void merge(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx==yy)
        return;
    a[xx]=yy;
}
int main()
{
    init();
    int n,k,count=0,d,x,y;
    int fx1,fx2,fx3;
    int fy1,fy2,fy3;
    scanf("%d%d",&n,&k);
    while(k--)
    {
        scanf("%d%d%d",&d,&x,&y);
        if(x>n||y>n||(d==2&&x==y))
        {
               count++;
               continue;
        }
        fx1=find(x),fx2=find(x+n),fx3=find(x+n*2);/*x的同类,吃x的,x吃的*/
        fy1=find(y),fy2=find(y+n),fy3=find(y+n*2);/*y的同类,吃y的,y吃的*/
        /*xy如果是同类,则x吃的不能是y(fx3!=fy1),吃x的不能是y(fx2!=fy1)*/
        /*xy如果是同类,则y吃的不能是x(fy3!=fx1),吃y的不能是x(fy2!=fx1)*/
        if(d==1)
        {
            if(fx3!=fy1&&fx2!=fy1&&fy3!=fx1&&fy2!=fx1)/*满足上述条件则将三组合并*/
            {
                merge(fx1,fy1);
                merge(fx2,fy2);
                merge(fx3,fy3);
            }
            else
                count++;
        }
        /*如果x吃y,则x不能和y是同类(fx1!=fy1),y吃的不能是x(fy3!=fx1),吃x的不能是y(fx2!=fy1)*/
        else
        {
            if(fx1!=fy1&&fy3!=fx1&&fx2!=fy1)
            {
                merge(fx1,fy2);
                merge(fx2,fy3);
                merge(fx3,fy1);
            }
            else
                count++;
        }
    }
    printf("%d\n",count);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation