欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - HDU3038
题意概括
有一个序列，共n个数，可正可负。
现在有m个结论。n<=200000,m<=40000
每个结论包括3个数a,b,s，表示序列中a~b的区间和为s。
现在让你依次判断结论的正确性。
如果当前结论与之前的矛盾，那么ans++，忽略该结论。
注意多组数据。
题解
这个差不多是带权并查集的板子题了……应该不用多说了。。
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=200005;
int n,m,fa[N],val[N];
int getf(int k){
if (fa[k]==k)
return k;
int res=getf(fa[k]);
val[k]+=val[fa[k]];
return fa[k]=res;
}
int main(){
while (~scanf("%d%d",&n,&m)){
for (int i=0;i<=n;i++)
fa[i]=i,val[i]=0;
int ans=0;
while (m--){
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
a--;
int Fa=getf(a),Fb=getf(b);
if (Fa==Fb)
ans+=(val[a]-val[b])!=s;
else {
fa[Fa]=Fb;
val[Fa]=-val[a]+s+val[b];
}
}
printf("%d
",ans);
}
return 0;
}