「JSOI2004」平衡点/吊打XXX

发表于 | 分类于 | | 浏览量： 次

这是一个欧皇与非酋的故事……

引言

很久很久以前，有一位欧皇叫做黄霖，他热衷于各种随机算法，而且每次都能AC，直到有一天，他看到了张老师（ZS，我的启蒙老师，他水平很高，造数据能力特强）出的一份卷子：

黄霖：嗯！T1模拟退火能AC！T2模拟退火也能AC！T3模拟退火照样AC！

张老师（冷笑）：嗯哼？三题都写模拟退火？有分吗？

然后就没有然后了呢poi…

传送门

洛谷P1337

题解

这是一道物理题。

首先根据最小势能原理，当整个系统的势能最小时，系统平衡。不要问我为什么QwQ，我物理不好呢poi

虽然这题的正解不是模拟退火，但是用这题来当模拟退火的经典题还是很不错的呢poi。

首先我们钦定一个点作为绳结所在的位置作为初始答案，然后计算势能。

每次都在当前答案点附近的一个区域内rand一个点，区域大小由当前温度决定，如果这个点更优（势能更小），那么久接收这个点作为答案。否则有一定的概率接收新答案（概率计算方法很玄学，但是温度越小接收的概率越大）。

然后将温度乘以一个降温系数（降温系数是一个小于1的正数，这一步即退火），然后进行下一次答案搜索。

当温度降到几乎为0时停止就行了呢poi。

退火技巧

首先可以多退几次。

降温系数要根据题目细调，太大了会导致时效差，太小可能搜不到最优解QwQ。

初始温度也要根据情况给定，可以用一些历史上特殊的日子，比如某dalao的生日来做初始温度呢poi。

种子也建议用某dalao的生日，或脸滚键盘，最好不要用初始值。

没事时多放放大悲咒，往生咒，般若波罗蜜多心经之类的音乐，你将得到佛祖的保佑。

代码

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
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1005;
const double delta=0.995;                   //降温系数
int n,X[maxn],Y[maxn],W[maxn];double ansx,ansy,anse;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline double PotentialEnergy(double nowx,double nowy)   //计算势能
{
	double ret=0;
	for(int i=1;i<=n;i++)
		ret+=sqrt((X[i]-nowx)*(X[i]-nowx)+(Y[i]-nowy)*(Y[i]-nowy))*W[i];
	return ret;
}
inline void SimulateAnneal(double T)
{
	double nowx=ansx,nowy=ansy;
	while(T>1e-14)
	{
		double tempx=nowx+(rand()*2-RAND_MAX)*T;
		double tempy=nowy+(rand()*2-RAND_MAX)*T;
		double PE=PotentialEnergy(tempx,tempy);
		if(PE<anse)                                   //如果更优就马上接受
		{
			ansx=tempx;ansy=tempy;
			nowx=tempx;nowy=tempy;
			anse=PE;
		}
		else if(exp((anse-PE)/T)*RAND_MAX>rand()){nowx=tempx;nowy=tempy;}  //否则有一定概率接收
		T*=delta;                              //降温
	}
}
inline void Solve()
{
	anse=PotentialEnergy(ansx,ansy);
	SimulateAnneal(2005);                     //多刷几次，记得洗把脸
	SimulateAnneal(1926);
	SimulateAnneal(1949);
	SimulateAnneal(1978);
}
int main()
{
	srand(20050429);//2005年4月29日dalao LTL出生，dalao会为你带来好运
	n=read();
	for(int i=1;i<=n;i++){X[i]=read();Y[i]=read();W[i]=read();}
	Solve();
	printf("%.3lf %.3lf\n",ansx,ansy);
	return 0;
}