【题解】P3416 [USACO16DEC]Moocast S

题目描述 Farmer John 有 N 头奶牛，他们想组建一个紧急的“传递信息”系统，以便相互之间传递重要的信 息。 他们决定使用对讲机来作为装备，而不是通过相互间的哞哞叫，每头牛配有一只对讲机。这些对讲 机都有自己的有限传输半径，如果有限传输半径是 P 的话，也就是说该对讲机能将信息传送到与之距离 不超过 P 的对讲机（请注意，奶牛 A 可能把信息传递给奶牛 B，但奶牛 B 却没办法把信息传递回去，因 为奶牛 A 的有限传输半径大于奶牛 B 的有限传输半径）。幸运的是,奶牛可以通过其他奶牛传递信息，所 以没必要每头牛都能直接传送到其他牛。 由于对讲机的这种不对等的性质，其中的一些奶牛传播效果可能比其他奶牛更有效，因为它们能传 递到更多的接收者（相互之间产生直接联系）。请帮助奶牛确定：如果源于一头牛，最多能将信息传递 到多少头牛？ 输入 第 1 行输入奶牛的个数 N； 第 2 到 N+1 行，第 i+1 行代表第 i 头奶牛的 Xi 和 Yi 坐标，以及其对应对讲机的最大传输半径 Pi。 输出 输出共一行一个整数，源于一头牛，最多能将信息传递到多少头牛？原始的这头牛也包含在内。 样例输入 Copy 4 1 3 5 5 4 3 7 2 1 6 1 1 样例输出 Copy 3 提示 对于 50%的数据： 1≤N≤100； 对于 100%的数据： 1≤N≤200； 0≤Xi,Yi,Pi≤30,000；

分析

看到这个数据范围，就会想到所有暴力都可以碾过去。 这道题需要注意一点： $A$到$B$并不能保证$B$也到$A$. 所以就不能并查集了。

考虑搜索

如果下一个点可以被到达，且之前没有到过，则搜索下去，并标记。 然后搜索完再统计答案。

对于距离计算

直接数学公式即可 $$di{s}_{i,j}=\sqrt{(a_{1_i}-a_{2_i}{)}^2+(a_{1_j}-a_{2_j}{)}^2}$$

代码

#include<bits/stdc++.h> using namespace std; int n,vis[209],ans; struct node{int x,y,p;}a[209]; inline double dis(register node a,register node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} inline void dfs(register int cur){for(register int i=1;i<=n;i++)if(dis(a[cur],a[i])<=a[cur].p&&!vis[i])vis[i]=1,dfs(i);} int main(){ scanf("%d",&n); for(register int i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].p); for(register int i=1;i<=n;i++){ register int cnt=0;memset(vis,0,sizeof(vis));vis[i]=1,dfs(i); for(register int j=1;j<=n;j++)if(vis[j])cnt++;ans=max(ans,cnt); }printf("%d\n",ans); return 0; }