解题思路转自：http://blog.csdn.net/azheng51714/article/details/8500459

分析：这是一道比较简单地并查集题目。

（1）弄清题意，找出出现冲突的位置，判断冲突很简单就是当两个人在同一行坐，同时他们到根节点的距离差值正好是他们之间的差值，此时就出现了冲突了。

（2）关键有两个地方，这也是并查集题目的难点，就是压缩集合，和求节点到根的距离。这里压缩集合就很简单了，一个通用的递归。求到跟的距离dist[a]+= dist[tem]; dist[rb]=dist[a]+x-dist[b];注意这两行代码，这是核心代码，首先第一行是求出节点a到根的距离。第二行代码使用的是数学中向量计算的原理如图

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50012;
int n,m,root[maxn],dis[maxn];
int find(int i){
    if(root[i]==i)return i;
    int ans=root[i];
    root[i]=find(root[i]);
    dis[i]+=dis[ans];//求出节点a到根的距离
    return root[i];
}
void Union(int u,int v,int root_u,int root_v,int x){
    root[root_v]=root_u;
    dis[root_v]=dis[u]+x-dis[v];//使用的是数学中向量计算
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        int i,j,u,v,dist,ans=0,cnt=0;
        for(i=0;i<=n;i++)
            root[i]=i,dis[i]=0;
        while(m--){
            scanf("%d%d%d",&u,&v,&dist);
            int x=find(u),y=find(v);
            if(x!=y)
                Union(u,v,x,y,dist);
            else
                if(dis[u]+dist!=dis[v])
                    ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Zjnu Stadium

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1221    Accepted Submission(s): 472

HDOJ 3047 带权并查集,布布扣,bubuko.com

HDOJ 3047 带权并查集

原文：http://www.cnblogs.com/wushuaiyi/p/3652137.html