NOIp2017奶酪————并查集_奶酪 noip 并查集

题解：本题主要考查并查集。
1.并查集：如果两个洞相交（或相切），就把它们连入一个集合，可以想象一个集合就是一条通道，如果通道存在元素与底部、顶部相连输出Yes
代码如下：

#include<iostream>
#include<cmath>
using namespace std;
long long fa[1010],x[1010],y[1010],z[1010],a[24242],b[23423];
int t,n,h,r,tot1,tot2,flag;
int find(int x) 
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
double dis(long long x1,long long x2,long long y1,long long y2,long long z1,long long z2)
{
    return sqrt(pow((x1-x2),2)+pow((y1-y2),2)+pow((z1-z2),2));
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        tot1=0,tot2=0;
        cin>>n>>h>>r;;
        for(int i=1;i<=n;i++)
        fa[i]=i;
        for(int j=1;j<=n;j++)
        {
            cin>>x[j]>>y[j]>>z[j];
            if(z[j]+r>=h)tot1++,a[tot1]=j;
			if(z[j]-r<=0)tot2++,b[tot2]=j;
            for(int k=1;k<j;k++)
            { 
                if(dis(x[j],x[k],y[j],y[k],z[j],z[k])<=r+r)
                {
                    int w=find(j),v=find(k); 
                    if(w!=v)fa[w]=v;
                }
            }
        }
        flag=0;
        for(int j=1;j<=tot1;j++) 
        {
            for(int k=1;k<=tot2;k++)
            {
                if(find(a[j])==find(b[k]))
                {
                    cout<<"Yes"<<endl;
					flag=1;break;
                }
            }
            if(flag==1)break;
        }
        if(flag==0)cout<<"No"<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54