HDU---3038(并查集好题)

对于x - y 的和为z认为y 比 （x-1）大z。

即对 x-1 和 y 建边构造并查集并维护每个点到其父节点的Sum值、

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
#define rep(i,n) for(int (i)=1;i<=(n);i++)
const int maxn = 210000;
int p[maxn];
int sum[maxn];
int find(int x,int& Sum){ //用Sum记录一路走到顶端的和。
   if(p[x] ==x){
      Sum = 0;
      return x;
   }
   else {
      p[x] = find(p[x],Sum);
      Sum+=sum[x];
      sum[x] = Sum;
      return p[x];
   }
}
int n,m;
int main()
{
    while(scanf("%d %d",&n,&m)==2){
       int cnt = 0;
       for(int i=0;i<=n;i++){
         sum[i] = 0; p[i]=i;
       }
       rep(i,m){
         int x,y,he;
         scanf("%d %d %d",&x,&y,&he);
         x--;
         int s1=0,s2=0;
         int px=find(x,s1),py=find(y,s2);
         if(px==py){
            if(s1 - s2 != he){
                cnt++;
            }
         }
         else{
             p[px] =py;
             sum[px]=he+s2-s1;
         }
       }
       printf("%d\n",cnt);
    }
    return 0;
}