D - How Many Answers Are Wrong——种类并查集-蒲公英云

D - How Many Answers Are Wrong——种类并查集

Bertha 。 2022-06-12 11:50 238阅读 0赞

Think:
1知识点：种类并查集+后缀和数组
2思考：当学习新的知识点的时候不理解的地方应该动手实现在纸上模拟实现进而提高理解

vjudge题目链接

可参考博客1（种类并查集）
可参考博客2
可参考博客3

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 4;
int n, m, f[N], sum[N];/*sum数组为后缀和数组:sum[x] = [ x, f[x] ]*/
void Init();
int get_f(int x);
int main(){
    int ans, i, l, r, w;
    while(~scanf("%d %d", &n, &m)){
        ans = 0;
        Init();
        for(i = 1; i <= m; i++){
            scanf("%d %d %d", &l, &r, &w);
            l -= 1;
            int t1 = get_f(l);
            int t2 = get_f(r);
            if(t1 == t2){
                if(sum[l]-sum[r] != w)
                    ans++;
            }
            else if(t1 < t2){
                f[t1] = t2;
                sum[t1] = sum[r] + w - sum[l];/*sum[t1] = [ t1, f[t1] ] = [t1, t2] = sum[r] + w - sum[l]*/
            }
            else if(t1 > t2){
                f[t2] = t1;
                sum[t2] = sum[l] - w - sum[r];/*sum[t2] = [ t2, f[t2] ] = [t2, t1] = sum[l] - w - sum[r]*/
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
void Init(){
    for(int i = 0; i <= n; i++){
        f[i] = i;
        sum[i] = 0;
    }
}
int get_f(int x){
    if(f[x] == x)
        return f[x];
    else {
        int t = f[x];
        f[x] = get_f(f[x]);
        sum[x] += sum[t];
        return f[x];
    }
}