思路: 带权并查集
分析:
1 题目要求的是错误的条件的个数，这一题还是比较简单的带权并查集
2 我们用rank[x]表示的x到跟节点的距离，那么对于x和y来说，如果x和y在不同集合那么把x和y合并，否则直接判断rank[x] == (rank[y]+val)%300
代码:
分析:
1 题目要求的是错误的条件的个数，这一题还是比较简单的带权并查集
2 我们用rank[x]表示的x到跟节点的距离，那么对于x和y来说，如果x和y在不同集合那么把x和y合并，否则直接判断rank[x] == (rank[y]+val)%300
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 50010;
int n , m , ans;
int father[MAXN];
int rank[MAXN];
void init(){
ans = 0;
memset(rank , 0 , sizeof(rank));
for(int i = 0 ; i <= n ; i++)
father[i] = i;
}
int find(int x){
if(father[x] != x){
int fa = father[x];
father[x] = find(fa);
rank[x] = (rank[x]+rank[fa])%300;
}
return father[x];
}
void solve(int x , int y , int val){
int fx = find(x);
int fy = find(y);
if(fx != fy){
father[fx] = fy;
rank[fx] = (rank[y]+val-rank[x]+300)%300;
}
else{
if((rank[y]+val)%300 != rank[x]){
ans++;
}
}
}
int main(){
int x , y , val;
while(scanf("%d%d" , &n , &m) != EOF){
init();
while(m--){
scanf("%d%d%d" , &x , &y , &val);
solve(x , y , val);
}
printf("%d\n" , ans);
}
return 0;
}
