HDU - 3038————带权并查集

曾经终败给现在 2023-06-15 13:26 23阅读 0赞

[D - How Many Answers Are Wrong][]  
开始还没看出来  
我们把他转换一下  
\[a,b\] 这个区间 和 为 s  
其实就是 sum\[0, b\] - sum\[0-,a-1\] == s.

这样就找到 b 与a-1 的关系

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 2e5+5;
    int par[maxn];// 表示根
    int value[maxn];// 表示 自己 和根的差值
    
    void init(int n)// 初始化并擦hi及
    { 
        for(int i = 0; i <= n; i++)
        { 
            par[i] = i;// 开始指向自己
            value[i] = 0; //
        }
    }
    
    int found(int x)// 寻找父亲
    { 
        if(x ==par[x])
        { 
            return par[x];
        }
        else
        { 
            int t = par[x];
            par[x] = found(t);// 更新父亲
            value[x] += value[t];//更新值
    
            return par[x];
        }
    
    }
    bool unite(int x, int y, int w)
    { 
        int rootx = found(x);
        int rooty = found(y);
    
        if(rootx == rooty)
        { 
            if(value[y]- value[x] == w)return true;
            else return false;
        }
        else if(rootx!= rooty)
        { 
            par[rooty] = x;
            value[rooty] = w - value[y];
            return true;
        }
    }
    
    int main()
    { 
        ios_base::sync_with_stdio(false);
    
        int n, m, wrong;
        while(cin>>n>>m)
        { 
            init(n);
            wrong = 0;
            for(int i = 0; i < m; i++)
            { 
                int a, b, w;
                cin>>a>>b>>w;//w 其实可以看成 前b个 与 前 a-1个 的差值
    
                if(!unite(a-1, b, w))
                { 
                    wrong++;
                }
    
            }
            cout<<wrong<<endl;
        }
        return 0;
    }

[D - How Many Answers Are Wrong]: http://acm.hdu.edu.cn/showproblem.php?pid=3038