dfs剪枝求调
  • 板块P1433 吃奶酪
  • 楼主outadaoki
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/8 11:27
  • 上次更新2025/2/8 11:27:56
查看原帖
dfs剪枝求调
1058082
outadaoki楼主2025/2/8 11:27
#include<bits/stdc++.h>
#define int long long
#define rep(i , l , r) for(int i = l ; i <= r ; i ++) 

using namespace std;

const int N = 1e7 + 5;

inline int read()
{
	char ch = getchar();
	int x = 0 , f = 1;
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -f;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0' , ch = getchar();
	}
	return x * f;
}

inline void write(int x)
{
	if(x < 0)
	{
		putchar('-');
		x *= -1;
	}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

int power(int a , int b)
{
	if(b == 0) return 1;
	int c = power(a , b / 2);
	c *= c;
	if(b % 2 == 1) c *= a;
	return c;
}

struct cheese
{
	int x , y;
	bool is_chosen;
}a[20];

struct _next
{
	int num;
	double cost;
}tmp[N];

int n = read() , d[20][20];

double ans;

double _distance(cheese _a , cheese _b)
{
	return sqrt((_a.x - _b.x) * (_a.x - _b.x) + (_a.y - _b.y) * (_a.y - _b.y));
}

bool cmp(_next _a , _next _b)
{
	if(_a.cost != _b.cost)
		return _a.cost < _b.cost;
	else
		return _a.num < _b.num;
}

void dfs(int _x , double _sum)
{
//	cout << _x << ' ';
	if(_sum >= ans)
	{
//		cout << _sum;
//		puts("");
		return;
	}
	bool ok = 1;
	int x = 0;
	rep(i , 1 , n)
	{
		if(i == _x) continue;
		if(a[i].is_chosen)
		{
			tmp[++ x].num = i;
			tmp[x].cost = d[_x][i];
			ok = 0;
		}
	}
	sort(tmp + 1 , tmp + x + 1 , cmp);
//	cout << _x << ' ' << _sum << ' ' << ok << '\n';
//	rep(i , 1 , x) cout << tmp[i].num << ' ';
//	puts("");
	rep(i , 1 , x)
	{
		if(tmp[i].num == 0) continue;
		a[_x].is_chosen = 0;
		dfs(tmp[i].num , _sum + tmp[i].cost);
		a[_x].is_chosen = 1;
		tmp[i].num = tmp[i].cost = 0;
	}
	if(ok)
	{
//		cout << _sum;
		ans = min(ans , _sum);
//		puts("");
	}
}

signed main()
{
	if(n) ans = N;
	rep(i , 1 , n) a[i].x = read() , a[i].y = read() , a[i].is_chosen = 1;
	rep(i , 0 , n)
	{
		rep(j , 0 , n)
		{
			if(d[j][i]) d[i][j] = d[j][i];
			else d[i][j] = _distance(a[i] , a[j]);
		}
	}
	dfs(0 , 0);
	printf("%.2f" , ans);
	return 0;
}
2025/2/8 11:27
加载中...