【洛谷p3958】奶酪

矫情吗；* 2021-11-14 11:10 436阅读 0赞

[奶酪【题目链接】][Link 1]

题前废话不知道说啥了啊qwq（越来越沉默寡言）

![1605606-20190705112254691-609612393.png][]

好了看题：

SOLUTION：

思路的话，大概是搜索，然后大概广搜？？？

![1605606-20190705112444516-1717584557.png][]

但是我们今天写深搜（也是听xcg大佬讲了以后的整理博）

首先先是读入，注意因为有多组数据，所以一定要记得**重新赋值**例如memset。

然后我们寻找可以从奶酪下表面进去的洞，显然当一个洞的高度z-r<=0时，就可以通过了；

for(int i=1;i<=n;i++){
        if(a[i].z-r<=0)
           vis[i]=1,dfs(i);
    }

然后我们可以尝试剪枝（然后亲测剪枝以后更慢了？？？）

剪枝：因为当你某一个不行时，比它高的显然都不行，那么直接break；

不加sort：![1605606-20190705113853422-276417339.png][]

加了sort： *![1605606-20190705113912327-1320776744.png][]*

然后搜索：

结束条件：某个点的高度z+r后>=h；同时标记bj=1；表示有解

然后枚举点（这里dfs保证每个点只枚举一次，因为是判断有解，所以不需要记路径也就不需要管不同路径的影响）

如果bj=1，那么表示已经搜到解了，不必再搜，直接break；

否则首先判断：

1.这个点有没有被访问过

2.这两个空间站是否连通（关于连通我们可以比较它们圆心之间的距离与两倍半径的大小关系，当距离小于两倍半径时，连通）

如果没有访问过并且连通，dfs这个枚举到的点，vis=1；

然后最后判断bj=1/0，对应Yes/No;

CODE:

#include<bits/stdc++.h>
    #define ll long long
    
    using namespace std;
    
    inline ll read(){
        ll ans=0;
        char last=' ',ch=getchar();
        while(ch>'9'||ch<'0') last=ch,ch=getchar();
        while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
        if(last=='-') ans=-ans;
        return ans;
    }
    
    ll t,n,h,r;
    bool vis[1001],bj;
    struct node{
        ll x,y,z;
    }a[1001];
    bool cmp(node a,node b){
        return a.z<b.z;
    }
    
    double dis(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2){
        return sqrt((double)(x1-x2)*(double)(x1-x2)+(double)(y1-y2)*(double)(y1-y2)+(double)(z1-z2)*(double)(z1-z2));
    }
    
    void dfs(ll k){
        if(a[k].z+r>=h){
            bj=1;
            return;
        }
        for(int i=1;i<=n;i++){
            if(bj) return;
            if(!vis[i]&&dis(a[i].x,a[i].y,a[i].z,a[k].x,a[k].y,a[k].z)<=2.0*r){
                vis[i]=1;
                dfs(i);
            }
        }
    }
    
    int main(){
        t=read();
        for(int T=1;T<=t;T++){
            n=read();h=read();r=read();
            bj=0;
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++){
                a[i].x=read();
                a[i].y=read();
                a[i].z=read();
            }
                
            sort(a+1,a+n+1,cmp);
            for(int i=1;i<=n;i++){
                if(bj) break;
                if(a[i].z-r<=0)
                  vis[i]=1,dfs(i);
                else break;
            }
            if(bj) printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zhuier-xquan/p/11137422.html

[Link 1]: https://www.luogu.org/problemnew/show/P3958
[1605606-20190705112254691-609612393.png]: /images/20211114/3f6168d60adc486ba1c187671d204b08.png
[1605606-20190705112444516-1717584557.png]: /images/20211114/6e6a56c7c2f34ec2bf82d3598336c422.png
[1605606-20190705113853422-276417339.png]: /images/20211114/02fb84192b5f467b9e934fb2c9aa0175.png
[1605606-20190705113912327-1320776744.png]: /images/20211114/282bcccfd82d458da1fa45fef51da6ed.png