题解 P3416 【[USACO16DEC]Moocast S】

· · 题解

个人认为没有DFS的必要。

由于数据很小，所以不需要担心被卡，O(n^3)绰绰由余。

第一遍二重循环存边，第二遍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;
}