社区讨论
并查集 60 分 求助 谢谢
P3958[NOIP 2017 提高组] 奶酪参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xhw3o
- 此快照首次捕获于
- 2025/11/20 12:25 4 个月前
- 此快照最后确认于
- 2025/11/20 12:25 4 个月前
比较简明的并查集代码
可能是哪里出现了错误
希望大佬能帮忙看一下
CPP#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
struct node
{
long long x;
long long y;
long long z;
}a[1010];
int T; //数据组数
int n; //空洞个数
long long h,r; //奶酪的高 空洞半径
int answer1[1010],answer2[1010],tot1=0,tot2=0;
int fa[1010];
int flag1=0,flag2=0,flag=0;
void qing()
{
tot1=0,tot2=0;
flag1=0,flag2=0,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)
{
if(x!=fa[x])
return fa[x]=find(fa[x]);
return fa[x];
}
void add(int x,int y)
{
int father1=find(x);
int father2=find(y);
if(father1!=father2)
fa[father1]=father2;
}
int main()
{
freopen("testdata6.in","r",stdin);
freopen("66.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
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;
}
}
if(flag1==0&&flag2==0)
{
printf("No");
printf("\n");
continue;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(jiao(i,j)<=2*r)
{
add(i,j);
}
}
}
for(int i=1;i<=tot1;i++)
{
for(int j=1;j<=tot2;j++)
{
if(fa[answer1[i]]==fa[answer2[j]])
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag==1)
{
printf("Yes");
printf("\n");
}
else
{
printf("No");
printf("\n");
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
十分感谢
回复
共 6 条回复,欢迎继续交流。
正在加载回复...