hdu 3038 （並查集）

題目大意：

給出m個詢問，問【l，r】之間的和 ，求出有多少次詢問不和之前的矛盾的。

思路分析:

用並查集記錄當前節點到根節點的和。

#include 
#include 
#include 
#include 
#define maxn 222222
using namespace std;

int set[maxn];
int sum[maxn];

int find(int x)
{
    if(x!=set[x])
    {
        int f=set[x];
        set[x]=find(set[x]);
        sum[x]+=sum[f];
    }
    return set[x];
}


int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=n;i++)set[i]=i,sum[i]=0;

        int ans=0;
        while(m--)
        {
            int l,r,s;
            scanf("%d%d%d",&l,&r,&s);
            l--;
            int xx=find(l);
            int yy=find(r);

            if(xx==yy)
            {
                if(sum[l]-sum[r]!=s)ans++;
            }
            else
            {
                set[xx]=yy;
                sum[xx]=sum[r]-sum[l]+s;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}