AT_abc328_f [ABC328F] Good Set Query

思路

带权并查集模板。

如果对于一个三元组 $(a,b,c)$ 如果它能够添加到 $S$ 中一定满足如下条件中的一条：

1. $X_a,X_b$ 满足其中有一个是「不确定」的。在这里 $X_i$「不确定」指 $X_i$ 没有与其它的任意 $X_j$ 有关系 。
2. $X_a,X_b$ 有间接或直接的关系，但是能计算出 $X_a - X_b = c$。

发现此类问题很像并查集维护的过程，于是用带权并查集维护每一个点到根节点的权值和 $val_i$。

发现 $val_i$ 表示的就是 $X_i - X_r$，其中 $r$ 表示的就是 $i$ 所在并查集的根节点。

然后对于第一种情况是很好处理的，对于第二种情况，只需计算 $val_a - val_b$ 与 $c$ 的关系即可。

Code

#include <bits/stdc++.h>  
#define re register  
#define int long long  
  
using namespace std;  
  
const int N = 2e5 + 10,M = 4e5 + 10;  
int n,m;  
int f[N],val[N];  
vector<int> v;  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline int find(int x){  
    if (f[x] != x){  
        int pf = f[x];  
        f[x] = find(f[x]);  
        val[x] += val[pf];  
    }  
    return f[x];  
}  
  
inline bool merge(int a,int b,int c){  
    int x = find(a),y = find(b);  
    if (x != y){  
        f[x] = y;  
        val[x] = val[b] - val[a] + c;  
        return true;  
    }  
    else return (val[a] - val[b] == c);  
}  
  
signed main(){  
    n = read();  
    m = read();  
    for (re int i = 1;i <= n;i++) f[i] = i;  
    for (re int i = 1;i <= m;i++){  
        int a,b,c;  
        a = read();  
        b = read();  
        c = read();  
        if (merge(a,b,c)) v.push_back(i);  
    }  
    for (auto u:v) printf("%lld ",u);  
    return 0;  
}