Farmer John 有 N 头奶牛，他们想组建一个紧急的“传递信息”系统，以便相互之间传递重要的信息。他们决定使用对讲机来作为装备，而不是通过相互间的哞哞叫，每头牛配有一只对讲机。这些对讲机都有自己的有限传输半径，如果有限传输半径是 P 的话，也就是说该对讲机能将信息传送到与之距离不超过 P 的对讲机（请注意，奶牛 A 可能把信息传递给奶牛 B，但奶牛 B 却没办法把信息传递回去，因为奶牛A 的有限传输半径大于奶牛 B 的有限传输半径）。幸运的是,奶牛可以通过其他奶牛传递信息，所以没必要每头牛都能直接传送到其他牛。由于对讲机的这种不对等的性质，其中的一些奶牛传播效果可能比其他奶牛更有效，因为它们能传递到更多的接收者（相互之间产生直接联系）。请帮助奶牛确定：如果源于一头牛，最多能将信息传递到多少头牛？
第 1 行输入奶牛的个数 N； 第 2 到 N+1 行，第 i+1 行代表第 i 头奶牛的 Xi 和 Yi 坐标，以及其对应对讲机的最大传输半径 Pi。
输出共一行一个整数，源于一头牛，最多能将信息传递到多少头牛？原始的这头牛也包含在内。
提示 对于 50%的数据： 1≤N≤100； 对于 100%的数据： 1≤N≤200； 0≤Xi,Yi,Pi≤30,000；
（不用说了吧） 先判断如果可以直接到达，就将边设为1。 第二遍判断两点之间是否可以到达。 最后统计答案。
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,t,ans,f[201][201]; struct node{ int x,y,w; }a[201]; inline double js(node a,node b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main(){ register int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(js(a[i],a[j])<=a[i].w) f[i][j]=1; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j&&i!=k&&j!=k&&f[i][k]&&f[k][j]) f[i][j]=1; for(i=1;i<=n;i++){ t=0; for(j=1;j<=n;j++) t+=f[i][j]; ans=max(ans,t); } printf("%d",ans); return 0; }其实思路不难，搜索后统计就行了。 关键点是在判断当下一个顶点可以被达到，而且以前没有被达到过时，就可以标记并递归。
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,t,ans,vis[201]; struct node{ int x,y,w; }a[201]; inline double js(node a,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 x){ register int i; for(i=1;i<=n;i++) if(js(a[x],a[i])<=a[x].w&&!vis[i]){ vis[i]=1; dfs(i); } } int main(){ scanf("%d",&n); register int i,j; for(i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); for(i=1;i<=n;i++){ t=0; memset(vis,0,sizeof(vis)); vis[i]=1; dfs(i); for(j=1;j<=n;j++) if(vis[j]) t++; ans=max(ans,t); } printf("%d",ans); return 0; }