题意：

N和M。有N个数。

M个回答：ai, bi, si。代表：sum(ai...bi)=si。如果这个回答和之前的冲突，则这个回答是假的。

问：M个回答中有几个是错误的。

 

思路：

如果知道sum(ai...bi)=si。假设下一个是sum(ai,ci)=sj。则sum(ai,ci)肯定也知道了。这很符合并查集的结构。

*：画个图。

 

代码：

int n,m;int fa[200005];int sum[200005];int findFa(int x){    if(fa[x]==x){        return fa[x];    }    int t=fa[x];    fa[x]=findFa(fa[x]);    sum[x]+=sum[t];    return fa[x];}int main(){    while(scanf("%d%d",&n,&m)!=EOF){        rep(i,0,n){            fa[i]=i;            sum[i]=0;        }        int ans=0;        while(m--){            int A,B,S;            scanf("%d%d%d",&A,&B,&S);            int fA=findFa(A-1);            int fB=findFa(B);            if(fA!=fB){                fa[fB]=fA;                sum[fB]+=(sum[A-1]+S-sum[B]);            }else{                if(sum[A-1]+S!=sum[B]){                    ++ans;                }            }        }        printf("%d\n",ans);    }    return 0;}