食物链 POJ - 1182 (带权并查集)-白红宇

食物链 POJ - 1182 (带权并查集)

阅读量：803 次

发布时间：2019-03-25

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

带权并查集（Union-Find with weights）是一种高效处理相对关系的数据结构，广泛应用于处理具有相对权值的集合操作问题。在本题中，我们需要解决一个包含三种动物的相对关系问题，凭着给定的m句话描述关系，判断其中有多少假话。每种假话会导致两个动物之间出现矛盾。

1.基本原理

带权并查集通过维护每个节点与其父节点之间的关系extension来处理相对关系。具体来说：

数组 v[i] 用于记录节点 i 与其父节点 fa[i] 之间的关系状态，取值如下：
- v[i]=0：表示节点 i 和 fa[i] 是同类。
- v[i]=1：表示节点 i 吃它的父节点 fa[i]。
- v[i]=2：表示节点 i 被 fa[i] 吃。

在路径压缩过程中，我们会更新 v[x] 的值，使其反映从 x 到 fa[x] 的整体关系。具体实现如下：

v[x] = (v[x] + v[fa[x]]) % 3

2.代码解析

#include 
   
    #include 
    
     using namespace std;#define ll long longconst int maxn = 5e5 + 7;const int INF = 1e9 + 7;int n, m;int fa[maxn];int v[maxn];int find(int x) {    if (fa[x] == x) return x;    int f = fa[x];    fa[x] = find(fa[x]);    v[x] = (v[x] + v[f]) % 3;    return fa[x];}bool Union(int x, int y, int k) {    int r1 = find(x);    int r2 = find(y);    if (r1 == r2) {        int w = (v[x] - v[y] + 3) % 3;        if (w == k) return 1;        else return 0;    }    fa[r1] = r2;    v[r1] = (v[y] + k - v[x] + 3) % 3;    return 1;}int main() {    scanf("%d %d", &n, &m);    for (int i = 1; i <= n; i++) fa[i] = i;    int ans = 0;    while (m--) {        int k, x, y;        scanf("%d %d %d", &k, &x, &y);        if (x < 1 || x > n || y < 1 || y > n) {            ans++;            continue;        }        if (!Union(x, y, k - 1)) ans++;    }    cout << ans << endl;    return 0;}

3.代码解读

初始化：

fa 数组初始化为每个节点的父节点。

v 数组初始化为 0，表示无初始关系。

查找操作find：

查找的过程中进行路径压缩，更新 fa[x] 到其根节点。

同时更新 v[x]，反映从 x 到根节点的整体关系。

并操作Union：

找到目标集合的根节点 r1 和 r2。

如果 r1 和 r2 已经存在关系，检查是否符合新关系 k，若不符则增加假话计数。

合并两个集合，并更新 v 数组，维护新的关系状态。

将 k 调整为 0-2 对应的关系状态（0 表示同类，1 表示被 eater 吃，2 表示 eater 被 eater 吃）后进行合并。

4.注意事项

路径压缩：平衡树的高度，降低后续操作的时间复杂度。

合并时的关系更新：确保并操作后关系状态的准确性。

矛盾检测：在已有关系的情况下，检查新关系是否一致。

5.应用场景

带权并查集适用于解决具有相对关系的数据问题，如群系关系、诸侯城国关系等。该算法能够高效处理多种关系状态，确保数据一致性和准确性。

6.总结

通过上述代码和逻辑分析，可以有效识别和统计给定条件下产生的假话数目。带权并查集的巧妙运用使得相对关系的处理变得高效且直观。

转载地址：http://ozjyk.baihongyu.com/

你可能感兴趣的文章