题意：给出一个n,m,n表示的是有n 个人，m表示的是 有m 对关系： 接下来输入的就是这m对关系，a,b,x；表示的是a，b相距x个距离；然后判断输入的是否与这个数的上面的数信息一致， 输出不一致的数目；
思路：用一个dist[ ]数组记录他到他的祖先的距离；然后对并查集合并的时候将rb的祖先赋给ra，然后就要对dist[rb]的值进行重新赋值，公式为dist[ rb ] = dist[a] x - dist[b],公式推导可以见下面这张图：
其中为了在找到他的祖先的的同时更新他们的各个dist【】的值，运用了递归；
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
typedef long long ll;
const int maxn = 100000 10;
ll dist[maxn];
ll n,m;
ll father[maxn];
void Init()
{
for(int i = 1; i <= n ; i )
{
dist[i] = 0;
father[i] = i;
}
}
ll finds(ll x)
{
if(father[x] == x)
return x;
int t = father[x];
father[x] = finds(father[x]);
dist[x] = dist[t];
return father[x];
}
void unions(ll a,ll b,ll ra,ll rb,ll distance)
{
father[rb] = ra;
dist[rb] = dist[a] distance - dist[b];
}
int main()
{
while( ~ scanf("%I64d%I64d",&n,&m) )
{
Init();
ll ans = 0;
for(int i = 1; i <= m ; i )
{
ll a,b,distance;
scanf("%I64d%I64d%I64d",&a,&b,&distance);
ll ra = finds(a);
ll rb = finds(b);
if(ra == rb)
{
if(dist[b] - dist[a] != distance)
ans ;
}
else unions(a,b,ra,rb,distance);
}
printf("%I64dn",ans);
}
return 0;
}
