题意：n个数，m次询问，每次问区间a到b之间的和为s，问有几次冲突
思路：带权并查集的应用，[a, b]和为s，所以a-1与b就可以确定一次关系，通过计算与根的距离可以判断出询问的正确性
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 200010;
int f[MAXN],arr[MAXN];
int m,n;
int find(int x) {
if (f[x] == x)
return x;
int tmp = find(f[x]);
arr[x] += arr[f[x]];
return f[x] = tmp;
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i <= n; i++)
f[i] = i;
memset(arr, 0, sizeof(arr));
int ans = 0;
for (int t = 0; t < m; t++) {
int a,b,s;
scanf("%d%d%d", &a, &b, &s);
a--;
int f1 = find(a);
int f2 = find(b);
if (f1 != f2) {
f[f2] = f1;
arr[f2] = arr[a]+s-arr[b];
}
else if (arr[b]-arr[a] != s)
ans++;
}
printf("%d\n", ans);
}
return 0;
}HDU - 3038 How Many Answers Are Wrong （带权并查集）,布布扣,bubuko.com
HDU - 3038 How Many Answers Are Wrong （带权并查集）
原文：http://blog.csdn.net/u011345136/article/details/36390411