How Many Answers Are Wrong

题意

给出一个区间的长度 N，及 M 个子区间和， 形如：x y z, 表示
子区间 [x, y] 的和为 z
如果一个“子区间和”与前面的“子区间和”冲突，即为错误（而且这个“子区间和”将在接下来的判断中被忽略）。
求总错误个数。
ps：这个题是多组数据

分析算法

这题考察点是带权并查集，对于每两个结点，既保存了他们的集合的关系，也会保存他们之间的权值。当我们join(a,b)时，他首先将a，b并入了同一个集合中，然后又保存了a，b分别到最顶端的距离，当我们要去查a，b的距离是多少的时候，就可以计算出来a到b的距离 = a到顶端的距离-b到顶端的距离，这里我们把a，b的距离认为是b-a，保存的其实是两个结点(后者到前者)的差值

分析题目

题中给出a到b的和是c，我们需要将其转换成差值，也就是a-1结点到b的距离差是c，这样之后我们用距离差来计算，就不会出问题了。
这题我参考了这篇博客：传送门

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;

int N,M;
int fa[maxn],sum[maxn];

void init(){
    for(int i = 0;i<=N;i++){
        fa[i] = i;
        sum[i] = 0;
    }
}
int find(int x){
    if(x != fa[x]){
        int f = fa[x];
        fa[x] = find(fa[x]);
        sum[x] += sum[f];
    }
    return fa[x];
}

void join(int x,int y,int v){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
        sum[fx] = v+sum[y]-sum[x];
    }
}
int main(){
    freopen("in.txt","r",stdin);
    int a,b,c;
    while(~scanf("%d%d",&N,&M)){
        init();
        int cnt = 0;
        while(M--){
            scanf("%d%d%d",&a,&b,&c);a--;
            if(find(a) == find(b)){
                if(sum[a]-sum[b] != c) cnt++;
            }else{
                join(a,b,c);
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}