当前位置： 移动技术网 > IT编程>开发语言>C/C++ > HDU 3038 How Many Answers Are Wrong(并查集)

HDU 3038 How Many Answers Are Wrong(并查集)

2018年10月25日  | 移动技术网IT编程  | 我要评论

高淳红网,h4399,陕西民办大学

题意

有n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的。

思路

sum[x]表示x到区间末尾的总和
则a到b的总和c 可以表示为sum[a]-sum[b+1] = c。

代码

#include
#include
#include
#include
#include
#define ll long long
using namespace std;

int sum[200009], fa[200009];

int find(int x)
{
    if(fa[x] == x)
        return x;
    int t = fa[x];
    fa[x] = find(fa[x]);
    sum[x] += sum[t];
    return fa[x];
}

void update(int x, int y, int a, int b, int c)
{
    if(x > y)
    {
        fa[y] = x;
        sum[y] = sum[a]-sum[b]-c;
    }
    else
    {
        fa[x] = y;
        sum[x] = sum[b]-sum[a]+c;
    }
}

int main()
{
    int len, n;
    while(~scanf("%d%d", &len, &n))
    {
        memset(sum, 0, sizeof(sum));
        for(int i=0; i<=200001; i++)
            fa[i] = i;
        int ans = 0;
        while(n--)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            b++;
            int x = find(a);
            int y = find(b);
            if(x == y && sum[a] != sum[b] + c)
                ans++;
            else if(x != y)
                update(x, y, a, b, c);
        }
        printf("%d\n", ans);
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网