您好,欢迎来到年旅网。
搜索
您的当前位置:首页bzoj 4749: [Usaco2016 Dec]Moocast dfs

bzoj 4749: [Usaco2016 Dec]Moocast dfs

来源:年旅网

→←


很水的dfs题

n^2的dfs,把每个点都当作起点跑一遍,最后取max


代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;

struct node{
	int x,y,p;
};

int n;
node a[220];
bool f[220];
int ans=0;

double cal(int x,int y){
	double d=sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)*1.0+(a[x].y-a[y].y)*(a[x].y-a[y].y)*1.0);
	return d;
}

int dfs(int x){
	f[x]=true;
	int sum=1;
	for(int i=0; i<n; i++){
		if(f[i] || x==i)continue;
		if(cal(i,x)<=a[x].p*1.0)sum+=dfs(i);
	}
	return sum;
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].p);
	for(int i=0; i<n; i++){
		memset(f,0,sizeof(f));
		ans=max(ans,dfs(i));
	}
	printf("%d\n",ans);
	
	return 0;
}


因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- oldu.cn 版权所有 浙ICP备2024123271号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务