【POJ-1988】Cube Stacking【带权并查集】

【POJ-1988】Cube Stacking【带权并查集】

问题链接:https://vjudge.net/problem/POJ-1988

Solution:

叠箱子,一种想法是,使用双向链表,完全模拟这一过程,但是会超时,我们该用并查集解决。使用并查集的核心是,需要另外记录每个位置的高度,我们重新审视一下合并操作,将一个box A堆叠到另一个box B上,那么A的高度变成1,B的高度依旧是0;顺着这个思路,我们想尝试能否使用并查集记录某种值来解决,我们需要解决:

1.这个记录的值如何与查询的值联系起来

2.Union时如何更新这个值

3.find时如何更新(传播)这个值【通常Union后,合并前的某个根节点下的子结点的这个值没有更新,所以需要考虑如何在find时进行正确的更新】

首先,(1)可以被简单的设计出来,我们让一个点到其根节点的所有点上改值之和表示这个box下box的数量,这样显然也是可以通过路径压缩对路径上的这个值进行求和的,这样(3)find的更新细节也一并完成。

(2)如何Union,Union的时候,假设我们要将根A并到根B下方,显然需要将根A的这个值记录为根B下的结点数,对于根节点,我们可以使用负值表示根,那么这个负数具体是负几就可以用来记录这个树下有多少结点,这样合并的时候的值就正好可以设置成这个值的相反数。

代码:

#include <iostream>

using namespace std;

const int NIL = -1;
const int LIM = 30000;
struct Node {
    int parent, dist;
};
Node disSet[LIM];

inline char myGetChar() {
    char ret;
    while ((ret = getchar()) == ' ' || ret == '\n' || ret == '\t');
    return ret;
}

Node find(int x) {
    Node ret;
    if (disSet[x].parent < 0) {
        ret.parent = x;
        ret.dist = 0;
        return ret;
    }
    ret = find(disSet[x].parent);
    ret.dist += disSet[x].dist;
    disSet[x] = ret;
    return ret;
}

void Union(int x, int y) {
    x = find(x).parent;
    y = find(y).parent;
    if (x == y) return;
    disSet[x].dist = -disSet[y].parent;
    disSet[y].parent += disSet[x].parent;
    disSet[x].parent = y;
}

int main(void) {
    int p, x, y;
    char op;
    scanf("%d", &p);
    // init
    for (int i = 0; i < LIM; i++) {
        disSet[i].parent = NIL;
        disSet[i].dist = 0;
    }
    while (p--) {
        op = myGetChar();
        if (op == 'M') {
            scanf("%d%d", &x, &y);
            Union(x, y);
        } else {
            scanf("%d", &x);
            printf("%d\n", find(x).dist);
        }
    }
    return 0;
}

 

参考了:

https://www.youtube.com/watch?v=LfYiut7wYHI