P3958 【奶酪】

· · 题解

一篇并查集的题解qwq

说一下为什么会想到并查集

这道题简化一下就是看能不能从下表面（及其以下）某个地方能不能走到上表面（及其以上）某个地方

容易想到\quad在能相互到达的两个点（洞的球心）之间连边

然后看有没有一条从一个与底面相连的洞开始的能到上表面（或其以上）路径

（忽略掉括号里的话或许看起来更舒服？）

再来康一康这些边

它们只是用来维护连通性的

那么显然 直接用并查集会方便很多

实现时的一些奇技淫巧小技巧

首先显然要把能相互通达的洞维护一下

然后

我们阔以加两个点分别来表示上下表面

即n+1来表示下表面，n+2来表示上表面

然后胡乱维护一下（详细见代码）

最后查询n+1号点与n+2号点是否联通就OK了qwq

(一直查询一直爽

还有一些细节qwq

附上代码供大佬们参考qwqwq

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

inline int read() {
    int op = 1, a = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') op = -1;
    for (; c >= '0' && c <= '9'; c = getchar()) a = a * 10 + c - '0';
    return op * a;
}

const int maxn = 1003;
int T, n, h, r;
struct Point {int x, y, z;} poi[maxn];
struct DisjointSetUnion {
    int fa[maxn];
    void init(int _top) {for (int i = 1; i <= _top; i++) fa[i] = i;}//初始化
    int find(int u) {return (fa[u] == u) ? u : fa[u] = find(fa[u]);}
    void merge(int u, int v) {fa[find(u)] = find(v);}
} DSU;

int main() {
    T = read();
    for (; T; T--) {
        n = read(), h = read(), r = read(); long double d = r << 1; //d 为直径，r 为半径
        for (int i = 1; i <= n; i++) poi[i].x = read(), poi[i].y = read(), poi[i].z = read();
        DSU.init(n + 2); //初始化
        //用并查集维护能相互到达的洞
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                if (DSU.find(i) == DSU.find(j)) continue;
                int xx = poi[i].x - poi[j].x, yy = poi[i].y - poi[j].y, zz = poi[i].z - poi[j].z;
                double tmp = sqrt(1ll * xx * xx + 1ll * yy * yy + 1ll * zz * zz);
                // long double tmp = sqrtl(1ll * xx * xx + 1ll * yy * yy + 1ll * zz * zz);
                    //怕精度不够阔以用这一行
                if (tmp <= d) DSU.merge(i, j);
            }
        //再来维护一下这些洞与上下表面的连通性
        for (int i = 1; i <= n; i++) {
            if (poi[i].z <= r) DSU.merge(i, n + 1);
            if (poi[i].z + r >= h) DSU.merge(i, n + 2);
        }
        if (DSU.find(n + 1) == DSU.find(n + 2)) puts("Yes");
        else puts("No");
    }
    return 0;
}