洛谷P1433 吃奶酪——DFS，最优化剪枝

最新推荐文章于 2025-04-10 20:49:24 发布

www.sqyoj.club

最新推荐文章于 2025-04-10 20:49:24 发布

阅读量537

点赞数

本文链接：https://blog.csdn.net/qq_36314344/article/details/87075211

版权

本文详细解析洛谷P1433题目，采用深度优先搜索算法求解旅行商问题，通过剪枝优化搜索过程，避免不必要的计算，最终实现高效的解决方案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：https://www.luogu.org/problemnew/show/P1433

思路：

1、以（0，0）点为起点，进行深搜，相当于进行全排列。

2、最优化剪枝，如果得到的当前距离比已知的最小距离大了，跳出当前层的搜索，这样可以大大节省时间。

if(sum>minn)return;

3、不要与欧拉路、欧拉回路、哈密尔顿环混淆。

4、因为最多15个点，没有必要引入记忆化。

AC代码如下：

/*为保证精度，应该采用double，不能采用float，否则卡三个点*/ 
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n;
double x[16]={0},y[16]={0};
double minn=1e9,sum=0;
bool vis[16];

double dis(int a,int b){
	return sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
}

void dfs(int cns,int x){
	if(cns==n){
		minn=min(minn,sum);
		return;
	};
	if(sum>minn)return;/*最优化剪枝，否则TLE*/ 
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			vis[i]=1;
			sum+=dis(x,i);
			dfs(cns+1,i);
			/*回溯*/ 
			vis[i]=0;
			sum-=dis(x,i);
		}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
	vis[0]=1;
	dfs(0,0);
	
	printf("%.2f\n",minn);
}