题意

• 有一块奶酪，高度为h，内部有n个球洞，半径均为r,问这些球洞能否贯穿奶酪

思路

• 使用并查集，合并到顶和底两个大集合中，最后检查顶和底是否在同一个集合
• 注意，和顶部连通的球洞可能同时和底部连通，注意处理方式
• 另一种思路为使用深度优先搜索，看全部搜完后最大深度能否超过h

AC代码(并查集)

#include<bits/stdc++.h>
using namespace std;
typedef struct{
	long long x,y,z;
}C;
C a[1010];
int fa[1010];
long long n,h,r;
bool cmp(C x,C y){
	return x.z<y.z;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
long long dis(int p,int q){
	return (a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y)+(a[p].z-a[q].z)*(a[p].z-a[q].z);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		//n为底，n+1为顶
		scanf("%lld%lld%lld",&n,&h,&r);
		for(int i=0;i<n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
		for(int i=0;i<=n+1;i++)	fa[i]=i;
		for(int i=0;i<n;i++){
			if(r*r>=a[i].z*a[i].z) {merge(i,n);}
			if(r*r>=(a[i].z-h)*(a[i].z-h)){merge(i,n+1);}//注意一个洞可以同时贯通顶部和底部
			for(int j=0;j<n;j++){
				if(i!=j&&dis(i,j)<=4*r*r){
					merge(i, j);
				}
			}
		}
		if(find(n)==find(n+1))printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}