How Many Answers Are Wrong HDU

#include<iostream>
#include<cstring>
using namespace std;
const int N=200010;
int d[N],p[N];
int find(int x)
{
    if(p[x]!=x)
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}
int main()
{
    int n,m,a,b,sum;
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            p[i]=i;
        int ans=0;
        memset(d,0,sizeof d);
        while(m--)
        {
            cin>>a>>b>>sum;
            a--;
            int pa=find(a);
            int pb=find(b);
            //把b的父节点接到a的后面
            //p(a)<---a<---p(b)<---b
            //a到p(a)为da,b到p(b)为db,b到a为sum 
            //那么p(b)到p(a)为 d[a]-d[b]+sum
            //就相当于大的点-小的点,好理解 
            
            //如果把a的父节点接到b的后面
            //父节点和子节点要颠倒了,不易理解 
            if(pa!=pb)
            {
                p[pb]=pa;
                d[pb]=d[a]-d[b]+sum;
            }
            else if(d[b]-d[a]!=sum)
                ans++;
        } 
        cout<<ans<<endl;
    }
}
原文地址:https://www.cnblogs.com/QingyuYYYYY/p/12249160.html