[数据结构与算法]奶酪（巧用并查集）

原题

思路

• 从题意来看明显可以使用宽搜
• 但是也可以从集合的角度应用并查集求解（从大佬的博客受到启发）
• 将能连在一起的洞看作一个集合
• 最后判断是否有一对通向底部并且通向顶部的点在同一个集合
• 有的话即课满组题意所需条件

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
typedef long long ll;
//不用long long会爆掉

ll n, m, t;
ll x[N], y[N], z[N];
ll p[N];
ll f1[N], f2[N];

ll findx(ll x)
{
    if(p[x] != x) p[x] = findx(p[x]);
    return p[x];
}

ll get_dist(ll a1, ll a2, ll a3, ll b1, ll b2, ll b3)
{
    return (a1 - b1) * (a1 - b1) + (a2 - b2) * (a2 - b2) + (a3 - b3) * (a3 - b3);
}

int main()
{
    cin >> t;

    while(t --)
    {
        ll n, h, r;
        cin >> n >> h >> r;
        ll top = 0, bom = 0;

        for(ll i = 1; i <= n; i ++) p[i] = i;

        for(ll i = 1; i <= n; i ++)
        {
            cin >> x[i] >> y[i] >> z[i];

            if(z[i] - r <= 0)
            {
                f1[bom ++] = i;
            }
            if(z[i] + r >= h)
            {
                top ++;
                f2[top ++] = i;
            }

            for(ll j = 1; j <= i; j ++)
            {
                if((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) > 4 * r * r) continue;
                if(get_dist(x[i], y[i], z[i], x[j], y[j], z[j]) <= 4 * r * r)
                {
                    ll a = findx(i), b = findx(j);
                    if(a != b) p[a] = b;
                }
            }
        }

        ll s = 0;
        for(ll i = 0; i < top; i ++)
        {
            for(ll j = 0; j < bom; j ++)
            {
                if(findx(f1[j]) == findx(f2[i]))
                {
                    s = 1;
                    break;
                }
            }
            if(s) break;
        }

        if(s) puts("Yes");
        else puts("No");
    }

    return 0;
}