题解 P3416 【[USACO16DEC]Moocast(silver)奶牛广播-银】

· · 题解

题意

求从一个点出发最多可以访问到的点数

算法

1、Floyd。

此解法详见其他题解。

2、DFS（我的方法）

不要轻视DFS，在本题中TA的效率为O(n^2)，而Floyd的效率仅为O(N^3)，碾压。

方法为从一个点出发DFS，搜到点就tot++，比较tot和ans。

存边时我采用的是邻接表，为了在DFS中减少循环。

至于处理能否到达，可以用一个巧妙的方法：

题目意思是如果sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))<=p[i]成立，则 i 可以到 j，但小数运算十分讨厌，我们可以两边同时平方来处理，转变为sqr(x[i]-x[j])+sqr(y[i]-y[j])<=p[i]*p[i]。

以下为代码：

#include<cstdio>
int n,ans,tot,x[205],y[205],p[205],edge[205][205];
bool v[205];
inline int sqr(int x){return x*x;}
void dfs(int k){
    if(v[k])return;
    v[k]=1;tot++;
    for(register int i=1;i<=edge[k][0];i++)dfs(edge[k][i]);
}
int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)scanf("%d%d%d",x+i,y+i,p+i);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++)
            if(sqr(p[i])>=sqr(x[i]-x[j])+sqr(y[i]-y[j]))
                edge[i][++edge[i][0]]=j;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++)v[j]=0;
        tot=0;
        dfs(i);
        if(tot>ans)ans=tot;
    }
    printf("%d",ans);
}