剪枝dfs+卡次数,hack两个wa,怎么卡时间?
  • 板块P1433 吃奶酪
  • 楼主wh_up
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/27 12:15
  • 上次更新2024/3/27 16:29:53
查看原帖
剪枝dfs+卡次数,hack两个wa,怎么卡时间?
983436
wh_up楼主2024/3/27 12:15
#include<cstdio>
#include<math.h>

using namespace std;

int n, tag[16], cnt, ma = 0; // cnt表示还未访问的点数 
double loc[16][2], ans = 1e5, sum = 0;

void dfs(double x, double y)  
{
	if(!cnt){
		ans = sum < ans ? sum : ans; // 取小值
		return; 
	}
	ma++;
	if(ma >= 10000000)  // 卡次数
		return;
	for(int i = 1; i <= n; i++){  // 枚举n个点 
		double d; 
		if(tag[i] == 0){  // 当前点没有被访问过 
			
			d = sqrt(pow(x-loc[i][0], 2) + pow(y-loc[i][1], 2));
			sum += d;
			if(sum >= ans){  // 剪枝
				sum -= d;				
				continue;    
			}

			tag[i] = 1; // 标记
			cnt--;
			dfs(loc[i][0], loc[i][1]); // 进入该点 
			cnt++;
			sum -= d;
			tag[i] = 0; 
		} 
	}
}

int main(void)
{
	int i,j;
	scanf("%d", &n);
	cnt = n;
	for(i=1;i <= n; i++)	scanf("%lf %lf", loc[i], loc[i]+1);  
	dfs(0, 0);
	printf("%.2lf", ans); 
	return 0;
}
2024/3/27 12:15
加载中...