[Usaco2016 Dec]Moocast

原题链接https://www.lydsy.com/JudgeOnline/problem.php?id=4749

可以对于每个点(i)，往跟(i)距离小于等于(p[i])的点(j)都连一条边，表示(i)可以传输到(j)。然后由于图的规模最多(N^2=40000)，我们可以直接从每个点出发遍历一遍算出可以到达多少点。

建图复杂度(O(n^2))，搜索复杂度O(N^3)。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define maxn 210
using namespace std;
 
inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
 
vector<int> to[maxn];
int n,x[maxn],y[maxn],p[maxn],ans;
bool vis[maxn];
 
inline int dist(int i,int j){
    return (int)ceil(sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) ));
}
 
int dfs(int u){
    int size=1;
    vis[u]=true;
    for(register unsigned int i=0;i<to[u].size();i++){
        int v=to[u][i];
        if(!vis[v]) size+=dfs(v);
    }
    return size;
}
 
int main(){
    n=read();
    for(register int i=1;i<=n;i++) x[i]=read(),y[i]=read(),p[i]=read();
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++) if(i!=j){
            if(dist(i,j)<=p[i]) to[i].push_back((int)j);
        }
    }
    for(register int i=1;i<=n;i++){
        memset(vis,false,sizeof vis);
        ans=max(ans,dfs(i));
    }
    printf("%d
",ans);
    return 0;
}