当前位置:首页 > 其他 > 【NOI 2002】银河英雄传说(洛谷P1196)题解:并查集优化路径压缩算法详解

【NOI 2002】银河英雄传说(洛谷P1196)题解:并查集优化路径压缩算法详解

2天前

【NOI 2002】银河英雄传说(洛谷P1196)题解:并查集优化路径压缩算法详解 NOI 2002 银河英雄传说 洛谷P1196 并查集 路径压缩 动态集合合并 第1张

一、题目解读

银河英雄传说”是一道经典的动态集合合并问题。题目背景设定在星际战争中,要求处理两种指令:战舰合并(M)和距离查询(C)。需要维护多个战舰集合,支持快速合并操作,并计算同一集合内任意两战舰的距离。核心挑战在于高效处理大规模数据与动态变化,避免时间复杂度爆炸。

二、解题思路

采用并查集(Union-Find)算法解决该问题。关键在于设计三个核心数组

1. parent[]:记录每个战舰的父节点,实现集合划分;

2. dist[]:存储每个节点到父节点的距离,用于距离累加;

3. size[]:维护集合大小,辅助合并时的距离计算。

通过路径压缩与距离更新,将查询与合并的时间复杂度优化至近乎O(α(n))(α为阿克曼函数的反函数,实际接近常数)。

三、解题步骤

1. 初始化:每个战舰自成集合,父节点指向自身,距离与大小初始化为0和1。

2. 处理合并指令(M):

    找到两战舰的根节点;

    将较小集合的根节点连接到较大集合,更新距离与集合大小。

3. 处理距离查询指令(C):

    若两战舰根节点不同,则不在同一列,输出-1;

    若在同一列,通过路径压缩后的距离差计算实际距离(需考虑边界修正)。

4. 路径压缩优化:在查找根节点时,递归过程中将路径上所有节点直接连接到根节点,减少后续查询深度。

四、代码与注释

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

const int MAXN = 30010;  // 最大战舰数量

int parent[MAXN];  // 父节点数组
int dist[MAXN];    // 到父节点的距离
int size[MAXN];    // 集合大小

// 初始化并查集
void init() {
    for (int i = 1; i < MAXN; i++) {
        parent[i] = i;      // 每个节点初始为根节点
        dist[i] = 0;        // 初始距离为0
        size[i] = 1;        // 集合大小为1
    }
}

// 查找根节点,路径压缩+距离更新
int find(int x) {
    if (parent[x]!= x) {  // 若x非根节点
        int root = find(parent[x]);  // 递归查找根节点
        dist[x] += dist[parent[x]];  // 累加路径上所有距离
        parent[x] = root;            // 直接连接x到根节点
    }
    return parent[x];
}

// 合并集合x和y
void merge(int x, int y) {
    int rootX = find(x);  // 找到x的根节点
    int rootY = find(y);  // 找到y的根节点
    if (rootX!= rootY) {  // 若不在同一集合
        parent[rootX] = rootY;          // 将x的根连接到y的根
        dist[rootX] = size[rootY];      // 更新距离:x根到新根的距离为y集合大小
        size[rootY] += size[rootX];     // 合并集合大小
    }
}

int main() {
    ios::sync_with_stdio(false);  // 加快IO速度
    cin.tie(nullptr);
    
    init();  // 初始化并查集
    
    int T;  // 指令总数
    cin >> T;
    while (T--) {
        char op;  // 指令类型
        int i, j;  // 战舰编号
        cin >> op >> i >> j;
        if (op == 'M') {
            merge(i, j);  // 执行合并
        } else {
            int rootI = find(i);  // 查找i的根节点
            int rootJ = find(j);  // 查找j的根节点
            if (rootI!= rootJ) {
                cout << -1 << "\n";  // 不同集合,输出-1
            } else {
                // 计算距离:dist[i]-dist[j]的绝对值-1(修正路径压缩导致的误差)
                int ans = abs(dist[i] - dist[j]) - 1;
                cout << (ans < 0? 0 : ans) << "\n";  // 确保结果非负
            }
        }
    }
    return 0;
}

五、总结

本代码通过并查集实现了高效的动态集合管理,利用路径压缩大幅降低查询与合并的时间成本。关键在于通过dist[]数组记录相对距离,并在合并时巧妙利用集合大小进行距离初始化。该解法不仅解决了“银河英雄传说”问题,也为其他涉及动态连通性查询的场景提供了优秀模板。建议读者深入理解路径压缩原理,并尝试优化其他类似问题,提升算法设计与实现能力。



原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。