题目大意
LOY有$n$台计算机，分别位于网格$(x_1,y_1), (x_2,y_2),\ldots,(x_n,y_n)$，他想安装一个路由器，使得所有的计算机通过路由器可以实现相互访问。也就是说，LOY布置了一个星型网络，所有的计算机都必须和路由器直接相连。
路由器安装的位置也必须是整数坐标，如何选择路由器的位置才能使得所需要的网线总和长度最小呢？
题目分析
寻找费马点，经典模拟退火问题。
待整理模拟退火学习笔记（并不想写，其实就是乱搞）。
本题数据很水，不设置向量仅仅按照粗糙的方向数组随机也能$A$。
爬山算法也能过。
代码
爬山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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const double pi=acos(-1),START_T=50000,END_T=1e-4,DELTA=0.98;
const int maxn=10005,DIV=20000;
struct Point {
double x,y;
} p[maxn];
int n;
double Dist(Point a,Point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double get_sum(Point x) {
double sum=0;
for(int i=1; i<=n; i++)sum+=Dist(p[i],x);
return sum;
}
int Anneal() {
Point ansp=p[1];
double t=START_T,ans=get_sum(ansp);
while(t>END_T) {
for(int i=0; i<4; i++) {
double ang=2*pi*(rand()%DIV)/DIV;
Point now;
now.x=ansp.x+cos(ang)*t;
now.y=ansp.y+sin(ang)*t;
double sum=get_sum(now);
if(sum<ans) {
ans=sum;
ansp=now;
}
}
t=t*DELTA;
}
return round(ans);
}
int main() {
srand(99995999);
while(~scanf("%d",&n)) {
for(int i=1; i<=n; i++) {
p[i].x=Get_Int();
p[i].y=Get_Int();
}
printf("%d\n",Anneal());
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const double pi=acos(-1),START_T=50000,END_T=1e-4,DELTA=0.98,P=0.4;
const int maxn=10005,DIV=20000;
struct Point {
double x,y;
} p[maxn];
int n;
double Dist(Point a,Point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double get_sum(Point x) {
double sum=0;
for(int i=1; i<=n; i++)sum+=Dist(p[i],x);
return sum;
}
int Anneal() {
Point ansp=p[1];
double t=START_T,ans=get_sum(ansp);
while(t>END_T) {
for(int i=0; i<4; i++) {
double ang=2*pi*(rand()%DIV)/DIV;
Point now;
now.x=ansp.x+cos(ang)*t;
now.y=ansp.y+sin(ang)*t;
double sum=get_sum(now);
if(sum<ans||exp(-t/START_T)<P) {
ans=sum;
ansp=now;
}
}
t=t*DELTA;
}
return round(ans);
}
int main() {
srand(99995999);
while(~scanf("%d",&n)) {
for(int i=1; i<=n; i++) {
p[i].x=Get_Int();
p[i].y=Get_Int();
}
printf("%d\n",Anneal());
}
return 0;
}
