DFS20分,样例能过,求救~
查看原帖
DFS20分,样例能过,求救~
236980
王炸拆开打楼主2020/9/17 21:06

谢谢大佬们

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
int n,T,vd;
LL h,r;
int vs[1001],vx[1001],vis[1001];
int aa[1001][1001];
struct stu{
	LL x,y,z;
}a[1001];
LL Oxyz_iCount(int p,int q) {return sqrt((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 dfs(int xx){
	if(vd) return 0;
	if(vs[xx]){
		vd++;
		return 0;
	}
	for(int i=1;i<=aa[xx][0];i++){
		int xxx=aa[xx][i];
		if(vd) break;
		if(!vis[xxx]){
			vis[xxx]=1;
			dfs(xxx);
			vis[xxx]=0;
		}
	}
}
int main(){
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		memset(aa,0,sizeof(aa));
		memset(vx,0,sizeof(vx));
		memset(vs,0,sizeof(vs));
		memset(vis,0,sizeof(vis));
		int head=0,c=0;vd=0;
		scanf("%d%lld%lld",&n,&h,&r);
		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>=h){vs[n]++;}
			if(a[i].z-r<=0){vx[++head]=i;}
		}	
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(2*r>=Oxyz_iCount(i,j)&&i!=j){
					int ccc=Oxyz_iCount(i,j);
					aa[i][++aa[i][0]]=j;
					aa[j][++aa[j][0]]=i;
				}
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=aa[i][0];j++){
//				printf("%d ",aa[i][j]);
//			}
//			printf("\n");
//		}
		for(int i=1;i<=head;i++){
			vd=0;
			vis[i]=1;
			dfs(vx[i]);
			if(vd) c++;
		}
		if(c) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
2020/9/17 21:06
加载中...