跳转至

银河英雄传说(NOI2002)

原题链接

题目详情

yhyxcs


算法和思路

并查集可以用于维护具有传递性关系的作用,每个集合的大小,绑定到根结点上,每个点到根结点的距离,绑定到每个元素的结点上。

我们定义 p[] 存储每个点的祖宗节点,d[] 存储 xp[x] 的距离,size[] 表示 x 所在集合的大小。

将第a列的船接到第b列的末尾,相当于让每个 a 列的船到 pa 的距离加上 size[pb],由于存储并查集中存在路径压缩的效果,因此只需要将 papb 的距离加上 size[pb] 即可,即 d[pa] = size[pb]

img


代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using i64 = long long;

const i64 N = 30010;

i64 n, m;
i64 p[N], size[N], d[N];

i64 find(i64 x) {
    if (p[x] != x) {
        i64 u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

void solve() {
    std::cin >> m;
    for (i64 i = 1; i <= 30000; i++) {
        p[i] = i;
        size[i] = 1;
    }

    char op;
    i64 x, y;
    while (m--) {
        std::cin >> op >> x >> y;

        i64 pa = find(x), pb = find(y);
        if (op == 'M') {
            d[pa] = size[pb];
            size[pb] += size[pa];
            p[pa] = pb;
        } else {
            std::cout << (pa == pb ? std::max(std::abs(d[x] - d[y]) - 1, 0ll) : -1) << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    solve();

    return 0;
}

运行结果

accept

回到页面顶部