题解：P10294

· · 题解

题解区已经有 BFS 的了，所以这是一篇带权并查集的题解。

思路

带权并查集

前置知识：并查集。

并查集模版题：P3367。

带权并查集，即边上带有特殊权值的并查集。

int find(int xx) {
    if(xx != fa[xx]) return fa[xx] = find(fa[xx]);
    return xx;
}
void unionn(int ta, int tb) {
    fa[ta] = tb;
    cc[tb] += cc[ta];  // 多出来的部分，对权值进行操作，注意方向，不能写反
    cc[ta] = 0;
    return;
}

可以发现，它只比普通的并查集多了对权值的运算。

具体做法

可以把每个边权设置为每个点的价值。

每次通过一个点去修改旁边的两个点，如果两个点都不是干草，那么合并，此时权值累加到一起，最终可以自动将图分成几个联通块，每个块都有一个祖先，最后输出所求位置的祖先的权值，即是答案。

注意

本题不能直接开二维数组，会 MLE，所以可以考虑转化为一位数组，再进行操作。

代码实现

#include <cstdio>
#include <cstring>
using namespace std;
int r, c, x, y;
char s[100005];
int a[100005], fa[100005], cc[100005];
int find(int xx) {
    if(xx != fa[xx]) return fa[xx] = find(fa[xx]);
    return xx;
}
void unionn(int ta, int tb) {
    fa[ta] = tb;
    cc[tb] += cc[ta];
    cc[ta] = 0;
    return;
}  // 带权并查集的操作
int main() {
    scanf("%d%d", &r, &c);
    for(int i = 0; i < r; ++i) {
        scanf("%s", s); // 读如字符串可以避免单个字符读入的一些问题
        for(int j = 0; j < c; ++j)
            a[i * c + j] = (s[j] == 'L' ? 10 : (s[j] == 'M' ? 5 : (s[j] == 'S' ? 1 : 0)));
    }
    for(int i = 0; i < r * c; ++i)
        fa[i] = i, cc[i] = a[i];
    scanf("%d%d", &x, &y);
    for(int i = 0; i < r * c; ++i) {
        if(!a[i]) continue;  // 这个判断很重要，只有两个都是南瓜才可以采集
        if(i % c != c - 1 && a[i + 1]) {
            int ta = find(i), tb = find(i + 1);
            if(ta != tb) unionn(ta, tb);
        }
        if(i < r * c - c && a[i + c]) {  // 边界条件
            int ta = find(i), tb = find(i + c);
            if(ta != tb) unionn(ta, tb);
        }
      // 向右与向下合并，因为向上和向左已经被合并过了
    }
    printf("%d\n", cc[find(x * c + y)]);
}