题意:给你一系列区间和,判断给出的区间中有几个是不合法的
分析:简单的带权并查集
sum[i] 代表 从 i 到父节点的距离
那么对于新加入的点 a , b
令 x = find(a),y=find(b),在这四个点中,只有 sum[y] 是未知的
那么求出 sum[y] = sum[a] + x - sum[b]
至于 a-- ,个人认为是为了防止区间重合,实现左闭右开
#include <cstdio> #include <iostream> #include <cstring> using namespace std; #define maxn 200000+10 int fa[maxn]; int n , m; int sum[maxn]; int find(int x) { if( fa[x] != x ){ int f = fa[x]; fa[x] = find(fa[x]); sum[x] += sum[f]; } return fa[x]; } int main() { while( cin >> n >> m ) { for(int i = 1 ; i <= n ; ++i)fa[i] = i; memset(sum,0,sizeof(sum)); int cnt = 0; for(int i = 1 ; i <= m ; ++i) { int a, b , c; scanf("%d %d %d",&a,&b,&c); a--; int x = find(a); int y = find(b); if( x == y ) { if( sum[b] - sum[a] != c ) cnt++; } else { fa[y] = x; sum[y] = sum[a] + c - sum[b]; } } cout << cnt << endl; } }