【luogu P1337】平衡点 / 吊打XXX(模拟退火)
xxx Luogu 模拟退火 吊打
2023-09-27 14:28:28 时间
平衡点 / 吊打XXX
题目链接:luogu P1337
题目大意
有 n 个重物,都系在一个足够长的绳子上,自上而下穿过桌面的一个洞,然后系在一起,然后问你绳结最后停在哪里。
绳结不会掉下洞口,绳子和桌面没有摩擦,桌子足够高。
思路
模拟退火大概就是利用了固体物质降温的过程,套用了热力学的理论。
然后流程是这样的:
一开始随便选一个答案求解,然后计算它和原本你最优答案的差。
如果比它优就直接接受,否则我们就看看这个答案能否被接受(Metropolis 准则,
−
d
e
l
t
a
/
t
-delta/t
−delta/t 的概率接受),然后我们就根据这个解往两边随机移动(移动的范围会越来越小,每次会乘上一个降温的系数 down)。
然后就是玄学代码了。
代码
#include<cmath>
#include<cstdio>
#include<cstdlib>
#define down 0.993
using namespace std;
struct node {
int x, y, w;
}a[1001];
int n;
double ansx, ansy, answ;
double energy(double x, double y) {
double re = 0, dx, dy;
for (int i = 1; i <= n; i++) {
dx = x - a[i].x;
dy = y - a[i].y;
re += sqrt(dx * dx + dy * dy) * a[i].w;
}
return re;
}
void sa() {
double t = 1999;
while (t > 1e-14) {
double ex = ansx + (rand() * 2 - RAND_MAX) * t;
double ey = ansy + (rand() * 2 - RAND_MAX) * t;
double ew = energy(ex, ey);
double delta = ew - answ;
if (delta < 0) {
ansx = ex; ansy = ey; answ = ew;
}
else if(exp(-delta / t) * RAND_MAX > rand()) {
ansx = ex; ansy = ey;
}
t *= down;
}
}
void work() {//多跑几次退火以找到答案
sa(); sa(); sa(); sa();
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].w);
ansx += a[i].x; ansy += a[i].y;
}
ansx /= n; ansy /= n;
answ = energy(ansx, ansy);
work();
printf("%.3lf %.3lf", ansx, ansy);
return 0;
}
相关文章
- java.io.IOException: Cleartext HTTP traffic to xxx.xxx.xxx.xxx not permitted
- Java变异出现错误:No enclosing instance of type XXX is accessible
- 正则表达式之Unicode 字符属性 Unicode Categories p{P} p{XXX}
- [DEPRECATION] Encountered positional parameter near xxx Positional parameter are considered deprecated; use named parameters or JPA-style positional parameters instead.
- Python脚本报错AttributeError: ‘module’ object has no attribute’xxx’解决方法
- Undeclared identifier:XXX
- [Issue Fixed]-不能为虚拟电脑xxx打开一个新任务
- 全网详细解决-bash: xxx: command not found的问题,比如-bash: telnet: command not found,以及详细说明yum和apt-get的区别
- The POM for XXX is invalid, transitive dependencies (if any) will not be available解决方案
- No symbol "xxx" in current context解决
- ROS学习笔记六:xxx.launch文件详解