大佬教程收集整理的这篇文章主要介绍了奶酪 noip dfs,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
题目:
https://ac.nowcoder.com/acm/problem/16417
dfs或者并查集
数据要开到long long
#include<iostream> #include<String.h> using namespace std; int mp[1002][1002],vis[1002]; long long n,h,r; struct node { long long x,y,z; }a[1002]; int dfs(int x,int t) { if(x==t) return 1; vis[x]=1; for(int i=1;i<=n+1;i++) { if(!vis[i]&&@H_538_10@mp[x][i]) { if(dfs(i,t)) return 1; } } return 0; } int xianglian(node q,node w) { return (q.x-w.X)*(q.x-w.X)+(q.y-w.y)*(q.y-w.y)+(q.z-w.z)*(q.z-w.z)<=4*r*r; } int main() { int t; cin>>t; while(t--) { cin>>n>>h>>r; memset(vis,0,sizeof(vis)); memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++) {Cin>>a[i].x>>a[i].y>>a[i].z; if(a[i].z<=r) mp[0][i]=1; if(h-a[i].z<=r) mp[i][n+1]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j&&xianglian(a[i],a[j])) mp[i][j]=1; } } if(dfs(0,n+1)) cout<<"Yesn"; else cout<<"Non"; } }
#include<iostream> using namespace std; long long n,h,r; int f[1200]; struct node { long long x,y,z; }a[1200]; int find(int X) { return x==f[x]?x:f[x]=find(f[x]); } int xianglian(node q,node w) { return (q.x-w.X)*(q.x-w.X)+(q.y-w.y)*(q.y-w.y)+(q.z-w.z)*(q.z-w.z)<=4*r*r; } void merge(int i,int j) { int fx=find(i); int fy=find(j); if(fx==fy) ; else f[fx]=fy; } int main() { int t; cin>>t; while(t--) { cin>>n>>h>>r; for(int i=0;i<=n+1;i++) f[i]=i; for(int i=1;i<=n;i++) {Cin>>a[i].x>>a[i].y>>a[i].z; if(a[i].z<=r) merge(0,i); if(h-a[i].z<=r) merge(i,n+1); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j&&xianglian(a[i],a[j])) { merge(i,j); } } } if(find(0)==find(n+1)) cout<<"Yesn"; else cout<<"Non"; } }
以上是大佬教程为你收集整理的奶酪 noip dfs全部内容,希望文章能够帮你解决奶酪 noip dfs所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。