自动搬运

查看原文

来自洛谷，原作者为

	OfstAutomataMachine 蒟蒻

搬运于2025-08-24 21:48:47，当前版本为作者最后更新于2020-03-26 17:31:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

个人认为没有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;
}