【POJ - 2420】A Star not a Tree?

【POJ - 2420】A Star not a Tree?

题目大意：给出平面上的$n$个点，你需要找出一个点，使得这个点到各点的距离和最小，并输出这个最小距离和。

这道题需要用到模拟退火算法。首先任意取一个点$(x,y)$，然后设置一个最高温，让温度慢慢冷却。对于每个温度，对点$(x,y)$进行相应幅度的扰动，使其变为点$(x^{\prime },y^{\prime })$。判断新的点是否比原来的点更优。如果更优则更新，如果更劣则有一定概率更新。

code

#include
#include
#include
#include
#include
using namespace std;
int n,T=50;
long long ans;
double t0=10000,t1,t2=1e-6,k=0.98;
struct node{
	double a,b;
}w[105];
double f(double x,double y){
	long double re=0,tk=1;
	for(int i=1;i<=n;i++){
		re+=sqrt(tk*(x-w[i].a)*(x-w[i].a)+tk*(y-w[i].b)*(y-w[i].b));
	}
	return re;
}
double rd(double x){
	return rand()*1.0/RAND_MAX*x;
}
int main()
{
	srand(time(NULL));
	double tx,ty,tz,x=0,y=0,z,px=0,py=0,pz;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&w[i].a,&w[i].b);
	}
	t1=t0;
	pz=f(0,0);
	while(t1>t2){
		z=f(x,y);
		for(int i=1;i<=T;i++){
			tx=x+(rand()%2*2-1)*t1;
			ty=y+(rand()%2*2-1)*t1;
			if(tx<-0.01||tx>10000.01||ty<0.01||ty>10000.01) continue;
			tz=f(tx,ty);
			if(tz<z){
				x=tx;y=ty;z=tz;
			}
			else{
				if(rd(1)<exp((z-tz)/t1)){
					x=tx;y=ty;z=tz;
				}
			}
			if(tz<pz){
				px=tx;py=ty;pz=tz;
			}
		}
		t1=t1*k;
	}
	if(px<0) px=0;
	if(px>10000) px=10000;
	if(py<0) py=0;
	if(py>10000) py=10000;
	ans=f(px,py)+0.5;
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61