是P3958吗
by Initialize02 @ 2018-09-23 18:59:48
### AC代码
```cpp
#include <bits/stdc++.h>
using namespace std;
struct node
{
long long x,y,z;
}a[1010];
long long h,r;
int T,n,answer1[1010],answer2[1010],fa[1010],tot1 = 0,tot2 = 0;
int flag1 = 0,flag2 = 0,flag = 0;
void qing()
{
tot1 = tot2 = flag1 = flag2 = flag = 0;
memset(a,0,sizeof(a));
memset(fa,0,sizeof(fa));
memset(answer1,0,sizeof(answer1));
memset(answer2,0,sizeof(answer2));
}
double jiao(int i,int j)
{
long long aa = (a[i].x - a[j].x) * (a[i].x - a[j].x);
long long bb = (a[i].y - a[j].y) * (a[i].y - a[j].y);
long long cc = (a[i].z - a[j].z) * (a[i].z - a[j].z);
return sqrt(aa + bb + cc);
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void add(int x,int y)
{
if (find(x) != find(y)) fa[find(x)] = find(y);
}
void readdata()
{
scanf("%d%lld%lld",&n,&h,&r);
qing();
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= n;i++)
{
scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
if(a[i].z-r <= 0){flag1 = 1; answer1[++tot1] = i;}
if(a[i].z+r >= h){flag2 = 1; answer2[++tot2] = i;}
}
}
void merge()
{
for(int i = 1;i <= n;i++)
for(int j = i + 1;j <= n;j++)
if(jiao(i,j) <= 2 * r) add(i,j);
}
void judge()
{
for(int i = 1;i <= tot1;i++)
for(int j = 1;j <= tot2;j++)
if(find(answer1[i]) == find(answer2[j])){flag = 1; break;}
}
int main()
{
scanf("%d",&T);
for(int i = 1;i <= T;i++)
{
readdata();
if(flag1 == 0 && flag2 == 0){printf("No\n"); continue;}
merge();
judge();
if(flag == 1) printf("Yes\n");
else printf("No\n");
}
}
```
帮你排了下版 顺便压了行
by Initialize02 @ 2018-09-23 19:31:19
主要是这个地方:
```cpp
fa[answer1[i]] == fa[answer2[j]]
```
应该是这样的:
```cpp
find(answer1[i]) == find(answer2[j])
```
不知道你在调试的时候有没有发现,假设有fa[1] = 2,又fa[2] = 2,如果这时将 集2 合并到 集3 中,**只有fa[2]会变为3,fa[1]仍然是2.** 尽管fa[1]应该也是3.
而find()函数在找爹过后,在返回上一层递归调用时会执行路径压缩,此时将更新fa[1]的值.所以如果按照你之前那样写,**会出现实际上两个借点已经处于同一棵树中,却被误判为不在同一棵树中的情况**,答案就错了.
by Initialize02 @ 2018-09-23 19:40:38
还有这几句放在最外层for循环外面,只能输出一个解的
```cpp
if(flag==1)
{
printf("Yes");
printf("\n");
}
else
{
printf("No");
printf("\n");
}
```
~~弱弱的问一句:同学你是不是把问题挂在这就吃饭去了呢 (逃~~
by Initialize02 @ 2018-09-23 19:46:54
@[Initialize02](/space/show?uid=109383) 因为你没有at 他
by 花花公纸他爹 @ 2019-08-02 15:31:31
@[高天昊](/space/show?uid=29214) 额
by 花花公纸他爹 @ 2019-08-02 15:31:41