题解 P3958 【奶酪】

谨以此题来纪念我爆炸的NOIp2017 ----------------------- 这个题虽然很多人说是并查集,但是搜索也是毫无压力的,考场搜索细节写挂,爆了个不上不下的80分。今天无意看到这道题，终于AC - 首先这道题要考虑一下精度问题,虽然出题人没有毒瘤的卡精度,但还是要值得注意。解决方法也很简单,去除开方运算,而是将半径平方,即$2r$ ---> $4r^2$,这样就OK了。不过要记得用$\rm long\;long$,不然会爆$\rm int$ - 然后考虑如何搜索,我是将每组数据用前向星存成图,然后搜这张图。这道题有一个很特别的地方,那就是它不用回溯,因为如果一个点到不了终点,那再次搜到的话也还是到不了终点,所以我们为什么要将它再搜一遍呢?直接丢掉就好了 上代码 ```cpp #include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; inline int read() //快读 { int k=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-')f=-1; for(;isdigit(c);c=getchar()) k=k*10+c-48; return k*f; } struct zzz{ //存空洞的坐标 ll x, y, z; }che[1001]; inline ll f(zzz x,zzz y) //计算空洞距离 { return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)+(x.z-y.z)*(x.z-y.z); } struct hhh{ //存图 int f, t, nex; }e[2000001]; int head[1001]; int tot; inline void add(int x,int y) //前向星 { e[++tot].f=x; e[tot].t=y; e[tot].nex=head[x]; head[x]=tot; } int s[1001],flag; bool en[1001],vis[1001]; //s:可以当作起点的空洞 flag:可以当作起点的空洞的个数 en:终点空洞 vis:这个点是否走过 bool ans; //判断能否到达上表面 void dfs(int str) //搜索主体 { if(en[str]) //找到终点就不用搜了 { ans=1; return ; } for(int i=head[str];i;i=e[i].nex) //向下寻找能搜的点 if(!vis[e[i].t]) { vis[e[i].t]=1; //直接标志为搜过,不再回溯 dfs(e[i].t); //向下搜索 if(ans) return ; } } int main() { int t; t=read(); int n; ll h,r; while(t--) { tot=0; memset(head,0,sizeof(head)); ans=0; flag=0; memset(en,0,sizeof(en)); memset(vis,0,sizeof(vis)); //清空所有变量 n=read(),h=read(),r=read(); for(int i=1;i<=n;i++) //输入数据 + 处理成图 { che[i].x=read(),che[i].y=read(),che[i].z=read(); if(che[i].z<=r) //如果z>=半径,那么这个空洞和下表面接触,将它加入起点 s[++flag]=i; if(che[i].z>=h-r) //同理,如果z>=h-r,那它和上表面接触,将它加入终点 en[i]=1; for(int j=1;j<i;j++) if(f(che[i],che[j])<=4*r*r) //防止精度损失 { add(i,j); add(j,i); } } // 搜索 + 输出 bool jjj=0; for(int i=1;i<=flag;i++) { dfs(s[i]); if(ans) { printf("Yes\n"); jjj=1; break; } } if(!jjj) printf("No\n"); } return 0; } ``` - 打个广告吧 　在下的[洛谷博客](https://www.luogu.org/blog/34188/)和[博客园博客](http://www.cnblogs.com/wxl-Ezio/)