题意：
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; }
hdu 3038 How Many Answers Are Wrong（并查集）
原文：http://www.cnblogs.com/fish7/p/4332623.html