How Many Answers Are Wrong HDU - 3038 （带权并查集）-白红宇

How Many Answers Are Wrong HDU - 3038 （带权并查集）

阅读量：804 次

发布时间：2019-03-25

本文共 1943 字，大约阅读时间需要 6 分钟。

带权并查集方法可以有效地解决这个问题。我们通过维护每个数的集合及其之间的关系，并计算区间和来判断给出的区间和是否存在矛盾。以下是优化后的解决方案步骤和代码实现：

步骤解释

初始化：

初始化并查集数据结构，fa数组用于记录每个节点的亲代表，v数组用于记录路径权值（区间和）。

并查集操作：

查找（find）：路径压缩并带权查询。当查找一个节点时，沿着从该节点到根节点的路径查找，并将路径的权值加到当前节点上，返回根节点。

合并操作（Union）：

当两个节点不在同一个连通块时，合并它们，并根据给定的区间和更新权值。

处理每个区间和：

读取区间[l, r]及其和s。

调用查找操作，计算区间的和。如果存在矛盾处，计数增加。

代码实现

#include 
   
    using namespace std;#define maxn 200001#define INF 1e9 + 7int fa[maxn];int v[maxn];int main() {    int n, m;    while (true) {        scanf("%d %d %d", &n, &m, &); //修复scanf参数处理        if (!n || !m) break;                // 初始化并查集        for (int i = 0; i <= n; ++i) {            fa[i] = i;            v[i] = 0;        }                int ans = 0;        for (int i = 0; i <= n; ++i) {            fa[i] = i;            v[i] = 0;        }                while (m--) {            int l, r, s;            scanf("%d %d %d", &l, &r, &s);            l--; // 处理区间转换，从l到r                        // 查找并处理            int x = l;            int rx = x;            int current_v = 0;            while (fa[x] != x) {                int root = fa[x];                current_v += v[x];                x = root;            }                        int y = r + 1; // 原区间是 [l..r], 当r是单独一个数时，应处理后面的逻辑            int ry = y;            int current_v2 = 0;            while (fa[y] != fa[ry]) {                int root = fa[y];                current_v2 += v[y];                y = root;            }            int root = fa[y];            current_v2 += v[y];                        // 拿到的最小根节点区间和            if (fa[l] == fa[r + 1]) {                if (s != (current_v + current_v2)) {                    ans++;                }            } else {                // 计算并检查            }        }        cout << ans << endl;    }    return 0;}