HDU--3308 How Many Answers Are Wrong-蒲公英云

HDU--3308 How Many Answers Are Wrong

末蓝、 2022-08-11 00:57 30阅读 0赞

这一道题是水题一道，但是我能说我做了将近三个小时吗。。。就是一直在纠结如何存储端点的值。在百思不得其解得的时候终于搜了一下，结果呵呵。把闭区间改成半开半闭区间不就完事了吗、、、剩下的完全就是加权并查集了。

下面的代码是让大的点做根，小的点做的是叶子，那么叶子的权值就是正值了。。。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define N 200005
int pa[N];
__int64 rank[N];
int find(int x)
{
    if(x!=pa[x])
    {
        int tmp=pa[x];
        pa[x]=find(tmp);
        rank[x]+=rank[tmp];
    }
    return pa[x];
}
int initial(int n)
{
    for(int i=0;i<=n;i++)
    {
        pa[i]=i;
    }
    memset(rank,0,sizeof(rank));//n在不大的情况下，它可能较费些时间
}
int main()
{
    int n,m,count;
    while(scanf("%d%d",&n,&m)==2)
    {
        count=0;
    initial(n);
    while(m--)
    {
        int x,y;__int64 Rank;//防止出现超过2^31 int越界，当然unsigned也行，不过到边的感觉让我没有安全感
        scanf("%d%d%I64d",&x,&y,&Rank);
        --x;
        int px=find(x),py=find(y);
        if(px!=py)
        {
            pa[px]=py;//取较大的点做根
            rank[px]=-rank[x]+rank[y]-Rank;//画一下，很容易明白
        }
        else
        {
            if(rank[y]-rank[x]!=Rank)
            count++;
        }
    }
    printf("%d\n",count);
    }
    return 0;
}