How Many Answers Are Wrong----hdu3038（并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3038

题意：数组第 a 个元素到第 b 个元素之间的和为sum；

求有几句话是假的，如果与前面的话有冲突就为假；

r[i]代表i的父节点到i的和；

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define N 201000
#define INF 0xfffffff
using namespace std;

int f[N],vis[N],r[N];

int Find(int x)
{
    int k = f[x];
    if(x != f[x])
    {
        f[x] = Find(f[x]);
        r[x] += r[k];
    }
    return f[x];
}
int main()
{
    int px, py, ans, i, n, m, x, y, sum;
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        for(i=0;i<=n;i++)
            f[i]=i,r[i]=0;
        ans = 0;
        while(m--)
        {
            scanf("%d%d%d", &x, &y, &sum);
            x --;
            px = Find(x);
            py = Find(y);
            if(px != py)
            {
                f[px] = py;
                r[px] = r[y] -r[x] - sum;
            }
            else if(r[y]-r[x] != sum)
                ans++;
        }
        printf("%d
",ans);
    }
    return 0;
}

上面的关系都是有方向的。。。

  代码中的123处均与*处有关，大家可以画个图有助于理解；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
#define N 202100
#define met(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f

int f[N], r[N];

int Find(int x)
{
    int k = f[x];
    if(x != f[x])
    {
        f[x] = Find(f[x]);
        r[x] += r[k];///1;
    }
    return f[x];
}

int main()
{
    int n, m, x, y, sum;

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

        int ans = 0;

        while(m--)
        {
            scanf("%d %d %d", &x, &y, &sum);
            x -- ;

            int px = Find(x);
            int py = Find(y);

            if(px != py)
            {
                f[px] = py;///*
                r[px] = r[y] - sum - r[x];///2;
            }
            else if(px == py && r[x]+sum != r[y])///3
                ans++;
        }
        printf("%d
", ans);
    }
    return 0;
}