题意
有 n 个整数（但不给出）， m 组条件，每组条件的格式为 (a, b, c)。即第 a 个数到第 b 个数之和为 c。如果某一组条件与前面的条件不矛盾，则认为它是真的。否则，则认为它是假的。问一共有几组假条件。
思路
a 到 b 的区间和为 c，可以看成是 a-1 到 b 的距离为 c。套用带权并查集的模板即可。
带权并查集
给条件（a， b， c），b 到 a 的距离为 c 。找矛盾条件。 增加权值数组 val，表示同一集合内到根节点的距离。初始化为 0。 由于带有方向性，去掉并查集原本的 rank 数组。 集合合并操作时，也要修改权值数组 val。但这里只修改被吞并的集合的根节点，其余节点在查询操作中更新。修改公式 val[ry] = val[x] + z - val[y]。这里可以把 x, y, ry 看成三个点，用向量的思想来理解。 查询根节点的操作，压缩路径时，除了更新 root 之外，也要更新权值。更新公式 val[x] += val[root[x]] 。即原值加上它的上一个根节点的权值，借助向量同样很好理解。 强力WA点见代码中！！！
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=3038
AC代码
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn =
2e5 +
10;
int n, m;
int x, y, z;
int res;
int root[maxn], val[maxn];
void init(
int n)
{
for(
int i=
0; i<= n; i++)
root[i] = i, val[i] =
0;
}
int Uf(
int x)
{
if(x == root[x])
return x;
int r = Uf(root[x]);
val[x] += val[root[x]];
root[x] = r;
return r;
}
void Union(
int x,
int y,
int z)
{
int rx = Uf(x), ry = Uf(y);
if(rx == ry)
return;
root[ry] = rx;
val[ry] = val[x] + z - val[y];
}
int main()
{
while(
scanf(
"%d %d", &n, &m) != EOF)
{
res =
0;
init(n);
while(m --)
{
scanf(
"%d %d %d", &x, &y, &z);
x --;
if(Uf(x) == Uf(y)){
if(val[y] - val[x] != z) res ++;
}
else Union(x, y, z);
}
cout << res << endl;
}
return 0;
}
