HDU 3038 How Many Answers Are Wrong（带权并查集）
题目大意就是有M个数，不知道它们具体的值，但是知道某两个数之间（包括这两个数）的所有数之和，现在给出N个这样的区间和信息，需要判断有多少个这样的区间和与前边已知的区间和存在矛盾。例如给出区间和[1,4]为20，[3,4]为15，再给出[1,2]为30，显然这个[1,2]的值就有问题，它应该为20-15=5。
这个题目需要分析什么时候会产生矛盾，不妨就具体看看上面的这个矛盾的例子
在这里这个图是画不了的，因为使用的都是闭区间，闭区间会加上端点的值，这就提醒我们这个题在处理的时候应该将闭区间的某一端变成开区间，比如将[1,4]变成(0,4]，将[3,4]变成(2,4]，将[1,2]变成(0,2]
如果已知(2,4]，(0,4]，那么(0,2]的值就可以求出来，如果说再给出(0,2]的值，而又不与(0,2]求出来的值相等，就产生了矛盾，这是矛盾产生的唯一情况：某个区间的值可以由前边的区间求出来，而又给出了这个区间错误的值。注意，有的地方对这个题的分析存在很大的误解，有的博客中说如果已知[1,10]为100，[1,5]为1000，[1,5]的值不可能大于100所以矛盾，这是不对的，因为本题题目中没有说所有的数都是正数，因此矛盾只有在不相等的时候产生。
那么需要考虑什么时候一个区间的值可以由之前的区间求出来呢？观察上边这张图，红色的这条边是求不出来的，而绿色的是可以求出来的，为什么呢？因为0、2属于同一个并查集，0、3不属于同一个并查集，因此不难得出本题的求解思路：如果给定区间的两个端点属于同一个并查集，判断这个区间的值是否与计算得到的值相等；如果给定区间的两个端点不属于同一个并查集，将这两个并查集合并。并查集边的权值就等于题干中的区间和。
这是我做的第一道带权值的并查集题目，现在理解的还不是很深刻，可能说的不是很清楚。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 201000;
int pre[maxn],sum[maxn],ans;
void Init(int n)
{
for(int i = 0;i <= n; i++)
{
pre[i] = i;
sum[i] = 0;
}
}
int getf(int x)
{
if(x != pre[x])
{
int t = pre[x];
pre[x] = getf(pre[x]);
sum[x] += sum[t];
}
return pre[x];
}
void join(int u,int v,int a)
{
int x = getf(u);
int y = getf(v);
if(x == y)
{
if((sum[u] - sum[v]) != a)
ans++;
}
else
{
pre[x] = y;
sum[x] = -sum[u] + sum[v] + a;
}
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m) != EOF)
{
Init(n);
ans = 0;
while(m--)
{
int l,r,s;
scanf("%d %d %d",&l,&r,&s);
// l--;
join(l,r,s);
}
printf("%d\n",ans);
}
return 0;
}