第一道正式的模拟退火。真香！

师兄说我又疯了

这道题要在二维平面上找一个点使这个系统稳定。

化学老师说：能量越低越稳定。这句话在物理也适用。

所以我们要做的就是使这些物品的重力势能尽可能低。

但是又不知道绳子长度啊！

傻瓜，只需要在桌子部分的绳子尽量长就可以了啊！

所以我们说到底要求的就是在二维平面上的一个点，满足\(\sum_{m_ig \times dist_i}\)最小。

遇到这种题：模拟退火！！！

我们SA主体的伪代码十分清晰：

设置初始温度T设置当前变量为x和y（这道题中）while T大于一个既定的温度值{ ???在原x基础上随机向左或向右移动，得到一个新解newx ???同理也得到一个newy ???// 注意：这里移动的幅度与当前温度T呈正相关，所以乘上去 ???????计算出新解和原解的优值之差DE// 优值就是答案更优更大的意思 ???if DE > 0 ???{ ???????当前变量和全局最优的变量都赋为这个新解 ???????当前最优值赋为新解的优值 ???} ???else if(exp(-DE / T) * RAND_MAX > RAND_MAX)// 意思是exp(-DE / T) 大于 1 ???{ ???????更新当前变量为这个新解，其他的不修改 ???} ???以一个delta来降温}

已经很清晰了，就不再解释了。

最后的一部分就是玄学调参。srand的数很重要。这关系到你是否能满分。。。

不过骗分的话就已经很赚了。

代码：

#include<cstdio>#include<cmath>#include<cstdlib>const int maxn = 1005;const double delta = 0.99;int n;struct Nodes{ ???int x, y, m;} s[maxn];int sumx, sumy;double ansx, ansy, ans;int read(){ ???int ans = 0, s = 1; ???char ch = getchar(); ???while(ch > ‘9‘ || ch < ‘0‘){ if(ch == ‘-‘) s = -1; ch = getchar(); } ???while(ch >= ‘0‘ && ch <= ‘9‘) ans = (ans << 3) + (ans << 1) + ch - ‘0‘, ch = getchar(); ???return s * ans;}double dist(double x, double y, double xx, double yy){ ???return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));}double cal(double x, double y){ ???double ret = 0; ???for(int i = 1; i <= n; i++) ret += s[i].m * dist(s[i].x, s[i].y, x, y); ???return ret;}void init_SA(){ ???ansx = (double)(sumx) / (double)(n); ???ansy = (double)(sumy) / (double)(n); ???ans = cal(ansx, ansy);}void SA(){ ???double x = ansx, y = ansy; ???double T = 2018; ???while(T > 1e-14)// 3965 ???{ ???????double newx = x + ((rand() << 1) - RAND_MAX) * T; ???????double newy = y + ((rand() << 1) - RAND_MAX) * T; ???????double newans = cal(newx, newy); ???????double DE = ans - newans; ???????if(DE > 0) ???????{ ???????????x = ansx = newx; y = ansy = newy; ???????????ans = newans; ???????} ???????else if(exp(-DE / T) * RAND_MAX > RAND_MAX) ???????{ ???????????ansx = newx; ansy = newy; ???????} ???????T = T * delta; ???}}int main(){ ???srand(19260817); ???srand(rand()); ???n = read(); ???for(int i = 1; i <= n; i++) ???{ ???????s[i].x = read(), s[i].y = read(), s[i].m = read(); ???????sumx += s[i].x; sumy += s[i].y; ???} ???init_SA(); ???for(int i = 1; i <= 10; i++) SA(); ???printf("%.3lf %.3lf\n", ansx, ansy); ???return 0;}

P1337 [JSOI2004]平衡点 / 吊打XXX

原文地址：https://www.cnblogs.com/Garen-Wang/p/9737443.html