HDU-3038.How Many Answers Are Wrong(带权并查集)

素颜马尾好姑娘i 2022-03-02 11:18 146阅读 0赞

# \[3038.How Many Answers Are Wrong)([http://acm.hdu.edu.cn/showproblem.php?pid=3038][http_acm.hdu.edu.cn_showproblem.php_pid_3038]) #

### 题目大意 ###

这题大概意思就是，通过前面所给区间的和，推算所给下一个区间的和的正确与否。

### Input ###

Line 1: Two integers, N and M (1 <= N <= 200000, 1 <= M <= 40000). Means TT wrote N integers and FF asked her M questions.

Line 2…M+1: Line i+1 contains three integer: Ai, Bi and Si. Means TT answered FF that the sum from Ai to Bi is Si. It’s guaranteed that 0 < Ai <= Bi <= N.

You can assume that any sum of subsequence is fit in 32-bit integer.

### Output ###

A single line with a integer denotes how many answers are wrong.

### Sample Input ###

10 5
    1 10 100
    7 10 28
    1 3 32
    4 6 41
    6 6 1

### Sample Output ###

### 带权并查集 ###

#include<cstdio>
    #include<cstring>
    const int maxn = 200000+5;
    int fa[maxn];
    int sum[maxn]; //表示根结点到子节点的和
    int n,m; //n个数，m个问题
    int find(int x)
    { 
        if(x!=fa[x])
        { 
            int root=find(fa[x]);
            sum[x]+=sum[fa[x]]; //权值合并
            fa[x]=root; //路径压缩
        }
        return fa[x];
    }
    void init() //初始化
    { 
        for(int i=1;i<=n;i++)
        { 
            fa[i] = i;
        }
    }
    int main()
    { 
        while(~scanf("%d%d",&n,&m))
        { 
            int ans=0;
            memset(sum, 0, sizeof(sum));
            init();
            for(int i=0;i<m;i++)
            { 
                int l,r,d; //l表示左边界，r表示右边界，d表示权值
                scanf("%d%d%d",&l,&r,&d);
                l--; //左闭右开区间
                int fl=find(l);
                int fr=find(r);
                if(fl!=fr) //该区间未能通过前面所给区间推出来
                { 
                    fa[fr]=fl;
                    sum[fr]=sum[l]-sum[r]+d;
                }
                else if(sum[r]-sum[l]!=d) 
                { 
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_3038]: http://acm.hdu.edu.cn/showproblem.php?pid=3038