记录编号	233174	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2016-03-04 10:25:02	内存使用	0.70 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=50005;
int father[maxn]={0};
int num[maxn]={0};
int N,K,ans=0;
int number(int x){//进行数的除三取余的工作
	x%=3;
	if(x<0)x+=3;
	return x;
}
int findroot(int x){
	if(father[x]==x)return x;
	int r=findroot(father[x]);//记录此时的根节点。
	num[x]+=num[father[x]];//将此节点与他的父亲节点的权重相加 
	return father[x]=r;//并树，把x的父亲节点改为根节点。
}
void deal(int x,int y,int k){//进行判断工作
	if(x>N||y>N){//最简单情况，当有>N 的情况
		ans++;
		return;
	}
	int ax=findroot(x),ay=findroot(y);
	if(ax==ay){//当根节点相同时，直接判断是否符合一个环的条件
		if(number(num[x]-num[y])!=k)ans++;
	}
	else{//根节点不同时，并树。
		num[ax]=number(num[y]-num[x]+k);
		father[ax]=ay;
	}
}
void work(){
	for(int i=1;i<=N;i++){
		father[i]=i;
	}
	for(int i=1;i<=K;i++){
		int r,a,b;
		scanf("%d%d%d",&r,&a,&b);r--;
		deal(a,b,r);
	}
	printf("%d",ans);
}
int main()
{
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	scanf("%d%d",&N,&K);
	work();
	return 0;
}