洛谷题目传送门
很可惜，充满Mo力的Mo拟退火并不是正解。不过这是一道最适合开始入手Mo拟退火的好题。
对模拟退火还不是很清楚的可以看一下
这道题还真和能量有点关系。达到平衡稳态的时候，物体的总能量应该是最小的。而总的能量来源于每个物体的重力势能之和。要想让某个物体势能减小，那就让拉着它的绳子在桌面下方的长度尽可能的长，也就是桌面上的要尽可能短。由此看来，某个物体的势能与桌面上的绳子的长度、物体重量都成正比。
于是，为了找到平衡点，我们要找一个点使得\(\sum_{i=1}^n d_i*w_i\)最小（\(d_i\)为\(i\)点到该点的距离）。
函数已经求出来了，接下来就是正常的模拟退火过程。注意一些细节就好了。
首先，初始解可以设成\(({\sum_{i=1}^n x_i\over n},{\sum_{i=1}^n y_i\over n})\)，可以更接近正解
解变动值最好随机两个值，\(\Delta x\)和\(\Delta y\)。随机变动距离和角度可能常数有点大。
然后就是调参数的问题了。蒟蒻太懒，于是就抄了YL据老的，此题参数普遍设大一点是合理的。
最后是写法问题。蒟蒻又学习了一招，知道有一个常数叫RAND_MAX，用于生成\([0,1)\)的随机值还是很方便的，在不同机子下可移植性也很强。（难怪Windows上rand出来的都是短整形数）
#include<cstdio>#include<cmath>#include<ctime>#include<cstdlib>#define RG register#define R RG double#define RD T*((rand()<<1)-RAND_MAX)//生成一个-T到T的随机变动距离const int N=1009;const double D=0.99,EPS=1e-15;int n;double x[N],y[N],w[N];inline double calc(R x0,R y0){//函数求值 ???R res=0,dx,dy; ???for(RG int i=1;i<=n;++i){ ???????dx=x[i]-x0;dy=y[i]-y0; ???????res+=sqrt(dx*dx+dy*dy)*w[i]; ???} ???return res;}int main(){ ???R T,avx=0,avy=0,start,x0,y0,x1,y1,res,ans,best,bx,by; ???RG int i,times=10; ???scanf("%d",&n); ???for(i=1;i<=n;++i){ ???????scanf("%lf%lf%lf",&x[i],&y[i],&w[i]); ???????avx+=x[i];avy+=y[i]; ???}//初始横纵坐标均选择平均值 ???best=start=calc(avx/=n,avy/=n);bx=avx;by=avy; ???srand(time(NULL)*clock()); ???while(times--){ ???????ans=start;x0=avx;y0=avy; ???????for(T=1000000;T>EPS;T*=D){ ???????????x1=x0+RD;y1=y0+RD; ???????????res=calc(x1,y1); ???????????if(best>res) ???????????????best=res,bx=x0,by=y0;//更新答案 ???????????if(ans>res||exp((res-ans)/T)*RAND_MAX<rand()) ???????????????ans=res,x0=x1,y0=y1;//接受新解 ???????} ???} ???printf("%.3lf %.3lf\n",bx,by); ???return 0;}洛谷P1337 【[JSOI2004]平衡点 / 吊打XXX】（模拟退火）
原文地址：https://www.cnblogs.com/flashhu/p/8900466.html