记录编号	104419	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.093 s
提交时间	2014-06-09 17:40:54	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=50010;
int N,K;
int ufs[SIZEN]={0};
int delta[SIZEN]={0};//和父亲的"生态位偏移量"
int ans=0;
int mod3(int x){
	x%=3;
	if(x<0) x+=3;
	return x;
}
int grand(int x){
	if(!ufs[x]) return x;
	int ans=grand(ufs[x]);
	delta[x]+=delta[ufs[x]];
	return ufs[x]=ans;
}
void deal(int x,int y,int k){//y的生态位一定比x大k(mod3意义下)
	if(x>N||y>N){
		ans++;
		return;
	}
	int gx=grand(x),gy=grand(y);
	if(gx==gy){
		if(mod3(delta[y]-delta[x])!=k) ans++;
	}
	else{
		delta[gx]=mod3(delta[y]-delta[x]-k);
		ufs[gx]=gy;
	}
}
void work(void){
	for(int i=1;i<=K;i++){
		int r,a,b;
		scanf("%d%d%d",&r,&a,&b);
		deal(a,b,r-1);
	}
	printf("%d\n",ans);
}
int main(){
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	scanf("%d%d",&N,&K);
	work();
	return 0;
}