记录编号 |
510296 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOI 2001]食物链 |
最终得分 |
100 |
用户昵称 |
leon |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.089 s |
提交时间 |
2018-09-18 21:32:26 |
内存使用 |
1.08 MiB |
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<stdio.h>
#define maxn (50005)
using namespace std;
int n,m,fa[4*maxn],ans;
void init()
{
for (int i=1;i<=4*n;i++)
fa[i]=i;
}
int find(int x)
{
if (fa[x]==x) return fa[x];
return fa[x]=find(fa[x]);
}
void unio(int x,int y)
{
fa[find(x)]=find(y);
return ;
}
int pan1(int x,int y)//判断 x与y是同类 是否是真话
{
if (x>n || y>n || x<=0 ||y<=0) return 0;
if (find(x+n)==find(y) || find(x+2*n)==find(y)) return 0;
//如果 x所吃的东西与y是同类 或 吃x的东西与y是同类,返回0(假话)
return 1;
}
int pan2(int x,int y)//判断 x吃y 是否是真话
{
if (x>n || y>n || x<=0 ||y<=0 || x==y) return 0;
if (find(x)==find(y) || find(x+2*n)==find(y)) return 0;
//x与y是同类,或,y与吃x的东西是同类,则返回0(是假话)
return 1;
}
int main()
{
freopen("eat.in","r",stdin);
freopen("eat.out","w",stdout);
scanf("%d%d",&n,&m);
init();ans=0;
for (int i=1;i<=m;i++)
{
int p,x,y;
scanf("%d%d%d",&p,&x,&y);
if (p==1)
{
if (pan1(x,y))
{
//要注意同时将三个集合全部重合
unio(x,y);
unio(x+n,y+n);
unio(x+2*n,y+2*n);
}
else
ans++;
}
else
{
if (pan2(x,y))
{
unio(x+n,y);//y与x吃的东西连接
unio(x+2*n,y+n);//y吃的东西与吃x的东西连接
unio(x,y+2*n);//x与吃y的东西连接
}
else
ans++;
}
}
printf("%d\n",ans);
}