洛谷P3958 奶酪（并查集）NOIP提高组2017年D2T1

题目链接
思路：
并查集
我们把所有空洞划分为若干个集合，一旦两个空洞相交或相切，就把它们放到同一个集合中。
我们还可以划出2个特殊元素，分别表示底部和顶部，如果一个空洞与底部接触，则把它与表示底部的元素放在同一个集合中，顶部同理。最后，只需要看顶部和底部是不是在同一个集合中即可。这完全可以通过并查集实现。
相关知识可以看此篇博客。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1005;
int fa[MAXN],rank[MAXN];
ll X[MAXN],Y[MAXN],Z[MAXN];
inline bool next_to(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2,ll r)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2) <= 4 * r * r;
    //判断两个空洞是否相交或相切
}
inline void init(int n)//初始化
{
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
        rank[i]=1;
    }
}
int find(int x)//找父亲
{
    return (x==fa[x])?(x):(fa[x]=find(fa[x]));
}
inline void merge(int i,int j)//合并
{
    int x=find(i),y=find(j);
    if(rank[x]<=rank[y])
        fa[x]=y;
    else
        fa[y]=x;
    if(rank[x]==rank[y]&&x!=y)//rank相同的两个合并秩会+1
        rank[y]++;
}
int main()
{
    int T,n,h;
    ll r;
    scanf("%d",&T);
    while(T--)
    {
        memset(X, 0, sizeof(X));
        memset(Y, 0, sizeof(Y));
        memset(Z, 0, sizeof(Z));
        scanf("%d %d %lld",&n,&h,&r);
        init(n);
        fa[1001] = 1001; //用1001代表底部
        fa[1002] = 1002; //用1002代表顶部
        for(int i = 1; i <= n; i++)
            scanf("%lld %lld %lld", X + i, Y + i, Z + i);
        for(int i=1;i<=n;i++)
        {
            if(Z[i]<=r)
                merge(i,1001);//与底部接触的空洞
            if(Z[i]+r>=h)
                merge(i,1002);//与顶部接触的空洞
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(next_to(X[i], Y[i], Z[i], X[j], Y[j], Z[j], r))
                   merge(i,j); //遍历所有空洞，合并相交或相切的球
            }
        }
        printf("%s\n",find(1001)==find(1002)?"Yes":"No");
    }
    return 0;
}

本文地址：https://blog.csdn.net/weixin_44063734/article/details/109260535