当前位置：首页 > 其他 > NOI 2001密码锁（洛谷P2024）解题全解析：并查集+关系标记算法实战

NOI 2001密码锁（洛谷P2024）解题全解析：并查集+关系标记算法实战

1天前

一、题目解读

2001年NOI密码锁（洛谷P2024）是一个经典的逻辑判断问题。题目描述了一个动物园中动物之间的关系，需要处理两种类型的陈述：同类关系（1）和捕食关系（2）。要求根据给定的K条关系，判断是否存在矛盾，并统计虚假陈述的数量。问题的核心在于如何高效地维护动态关系网络，并快速检测循环中的逻辑冲突。

二、解题思路

本题的突破点在于利用带关系标记的并查集（Disjoint Set Union with Relation Marking）。传统并查集通过合并集合判断连通性，但本题需要额外记录节点间的相对关系（同类、捕食）。因此，我们为每个节点引入关系值（0表示同类，1表示吃父节点，2表示被父节点吃），并在路径压缩时动态更新关系。通过维护关系的一致性，即可在合并时检测矛盾。

三、解题步骤

1. 初始化并查集：创建UnionFind类，初始化parent数组（每个节点指向自身）、rank数组（记录集合深度）、relation数组（初始关系均为0）。

2. 处理输入：遍历K条关系，对每条(x, y, type)进行合法性检查（如x、y是否越界，type=2时x≠y）。

3. 合并集合：

通过find()函数查找x和y的根节点，并路径压缩。

若根节点相同，则检查关系是否冲突（如x与y的关系与type是否矛盾）。

若根节点不同，按秩合并，根据type计算关系偏移量并更新relation值。

4. 统计虚假陈述：当检测到矛盾时，falseCount++。

5. 输出结果：最终输出falseCount。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 50010;

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    vector<int> relation; // 0:同类, 1:吃父节点, 2:被父节点吃
    
public:
    UnionFind(int n) : parent(n+1), rank(n+1, 0), relation(n+1, 0) {
        for(int i = 0; i <= n; ++i) {
            parent[i] = i; // 初始化每个节点为独立集合
        }
    }
    
    // 查找根节点并路径压缩
    int find(int x) {
        if(parent[x]!= x) {
            int orig_parent = parent[x];
            parent[x] = find(parent[x]); // 递归查找根节点
            relation[x] = (relation[x] + relation[orig_parent]) % 3; // 路径压缩时更新关系值
        }
        return parent[x];
    }
    
    // 合并两个集合
    bool unite(int x, int y, int type) {
        int rootX = find(x);
        int rootY = find(y);
        
        if(rootX == rootY) {
            // 检查关系是否冲突
            if((relation[x] - relation[y] + 3) % 3!= type) // 根据相对关系判断矛盾
                return false;
            return true;
        }
        
        // 按秩合并
        if(rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
            relation[rootY] = (relation[x] - relation[y] - type + 6) % 3; // 计算新关系值
        } else {
            parent[rootX] = rootY;
            relation[rootX] = (relation[y] - relation[x] + type + 3) % 3;
            if(rank[rootX] == rank[rootY]) {
                rank[rootY]++;
            }
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;
    
    UnionFind uf(N);
    int falseCount = 0;
    
    for(int i = 0; i < K; ++i) {
        int type, x, y;
        cin >> type >> x >> y;
        
        // 检查输入合法性（越界或自吃）
        if(x > N || y > N || (type == 2 && x == y)) {
            falseCount++;
            continue;
        }
        
        // 转换关系类型：1->0(同类), 2->1(捕食)
        int rel = (type == 1)? 0 : 1; 
        if(!uf.unite(x, y, rel)) { // 若合并时检测到矛盾，统计虚假
            falseCount++;
        }
    }
    
    cout << falseCount << endl;
}