题解
2024-08-08 16:19:25
发布于:安徽
21阅读
0回复
0点赞
个人认为没有DFS的必要。
第一遍二重循环存边,第二遍Floyd,第三遍统计结果。(主要注释见代码)
第二遍和第三遍好像可以合起来,留作读者自行思考。
喜闻乐见的代码:
#include<bits/stdc++.h>
using namespace std;
struct pos{
double x,y,p;//建议用double保留精度
} cow[201];
double dis(pos a,pos b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//求两点的欧几里得距离
}
int n,ans,con[201][201];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>cow[i].x>>cow[i].y>>cow[i].p;
for(int i=1;i<=n;i++)
for(int l=1;l<=n;l++)
con[i][l]=(dis(cow[i],cow[l])<=cow[i].p);//直接计算结果,返回1或0
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int l=1;l<=n;l++)
con[i][l]=con[i][l]||con[i][k]&&con[k][l];//可以直接这样写,偷懒利器
for(int i=1;i<=n;i++)
{
int vis=0;
for(int l=1;l<=n;l++)
vis+=con[i][l];
ans=max(ans,vis);//统计结果,更新ans
}
cout<<ans;
return 0;
}
这里空空如也
有帮助,赞一个