题解：P3958 [NOIP2017 提高组] 奶酪

· · 题解

涉及到集合的合并操作，可以使用并查集这个数据结构。

容易发现，可以把一个通道看成一个集合，答案就是这些集合能到达上下两端的通道数量了。问题就在于，如何对于洞口进行合并。

怎么样的两个洞可以合并呢？可以发现，如果两个圆的圆心的直线距离小于等于两个半径，即可以合并。

然后接着考虑怎么合并。我的想法是优先遍历编号小的洞，如果能合并就将祖先更新为它；之后再遇到别的洞就让他们祖先更新成自己祖先。这样一来，所有通道的有关信息都在编号最小的洞里了。

考虑设置两个数组，分别表示此结点及所在通道是否到达上方和到达下方。更新的时候，把祖先被更新的信息的洞的上下信息更新到自己祖先去即可。

最后遍历哪一个上下两方都有通道，大功告成！

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//fa为祖先信息
ll t, fa[10000 + 100];
//top代表到达顶上的，down代表到达底下的
bool top[10000 + 100], down[100000 + 10];
struct node {
    ll x, y, z;
} p[10000 + 100];
ll fin(ll x) {//板子
    if (fa[x] == x) return x;
    else return fa[x] = fin(fa[x]);
}
int main() {
    cin >> t;
    for (ll o = 1; o <= t; o++) {
        //多测不清空，原地见祖宗。。。
        memset(top, 0, sizeof top);
        memset(down, 0, sizeof down);
        for (ll i = 1; i <= 10000; i++) p[i].x = p[i].y = p[i].z = 0;

        ll n, h, r, ans = 0;//ans总计答案数量
        cin >> n >> h >> r;
        for (ll i = 1; i <= n; i++) fa[i] = i;//并查集初始化
        for (ll i = 1; i <= n; i++) {
            ll x, y, z;
            cin >> x >> y >> z;
            p[i].x = x;
            p[i].y = y;
            p[i].z = z;
            //一个可有可无的特判：如果只有一个，则看他能否到上面也能到下面
            if (n == 1) {
                ll rp = 0;
                if (p[i].z <= r) rp++;
                if (p[i].z >= h - r) rp++;
                if (rp == 2) cout << "Yes\n";
                else cout << "No\n";
            }
            bool flag = 1;//是否第一次连接
            if (p[i].z <= r) down[i] = 1;
            if (p[i].z >= h - r) top[i] = 1;
            //依次遍历之前所有的洞
            for (ll j = 1; j < i; j++) {
                //p就是直线距离，勾股定理求
                double q = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y) + (p[i].z - p[j].z) * (p[i].z - p[j].z));
                if (q <= 2 * r) {//可以合并
                    ll t1 = fin(i), t2 = fin(j);
                    if (flag) {//第一次连接
                        flag = 0;
                        fa[t1] = t2;
                        //根据定义，把自己的信息传递给祖先信息
                        if (!top[t2]) top[t2] = top[t1];
                        if (!down[t2]) down[t2] = down[t1];
                    } else {
                        //根据定义，把别人的信息传递给自己祖先信息
                        if (!top[t1]) {
                            top[t1] = top[t2];
                            top[t2] = 0;
                        }
                        if (!down[t1]) {
                            down[t1] = down[t2];
                            down[t2] = 0;
                        }
                        fa[t2] = t1;
                    }
                    //能到上面和下面
                    if (top[t2] && down[t2]) ans++;
                }

            }
        }
        //答案输出
        if (n != 1) {
            if (ans > 0) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}

代码较长，理解起来也还行。