hdu 3038 How Many Answers Are Wrong——带权并查集

hdu 3038 How Many Answers Are Wrong——带权并查集

题意：给定m行数据，没行数据有三个数a b c，表示区间【a，b】的和为c，求错误数据个数

思路：一开始用线段树写，写了一半发现没法进行区间更新，果断删掉换了并查集。我们默认根节点总是在数值小的那个节点上，那么一个区间的和就可以表示为val【b】 - val【a - 1】，其中权值通过并查集来维护，更新时的操作只要在纸上画两种区间情况就一目了然了

#include using namespace std;const int MAXN = 2 * 1e5 + 10;int N, M, par[MAXN], val[MAXN];int Query(int x) { if (x == par[x]) return x; int temp = par[x]; par[x] = Query(par[x]); val[x] += val[temp]; return par[x];}int main() { while (~scanf("%d %d", &N, &M)) { for (int i = 0; i <= N; i++) par[i] = i, val[i] = 0; int ans = 0; for (int i = 1; i <= M; i++) { int a, b, cost; scanf("%d %d %d", &a, &b, &cost); a--; int x = Query(a), y = Query(b); if (x == y) { if (val[b] - val[a] != cost) ans++; } else { if (x > y) { par[x] = y; val[x] = val[b] - val[a] - cost; } else { par[y] = x; val[y] = val[a] - val[b] + cost; } } } printf("%d\n", ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。