社区讨论

并查集 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 条回复,欢迎继续交流。

正在加载回复...