JSOI2004 平衡点 / 吊打XXX

题目描述

题解：

（这是模拟退火题解）

我走上模拟退火这条不归路的第一步

讲一下模拟退火：

物理上，温度骤降会导致材质的损坏，但是晶体的逐渐冷却过程趋于稳定。

这就有了模拟退火算法。

模拟退火的意思，就是先确定初始温度和一个降温系数，然后逐渐冷却，得出正确结果。

这里放一张图：

比如O是我们现在的位置，我们要去最低点（显然是右边最低）。

如果我们一直向更低点走，我们会到左边最低点。

这叫爬山算法，基于贪心。

但是这样只能得出局部最优，很难得到全局最优解。

怎么办呢？

于是你想到可以在一定区间内允许走向较高点，从而咸鱼翻身，逆转人生。

你就搞出了模拟退火算法。

附：

Au熔点：1067.18^。C

Ag熔点：961.78^。C

Cu熔点：1084.62^。C

W熔点：3421.85^。C

代码：

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1050
int n;
struct node
{
    double x,y,w;
}p[N];
double ax=0,ay=0,E;
double get_E(double x,double y)
{
    double ret = 0.0;
    for(int i=1;i<=n;i++)
    {
        double dx = x-p[i].x,dy = y-p[i].y;
        ret+=(double)p[i].w*(sqrt(dx*dx+dy*dy));
    }
    return ret;
}
const double d = 0.97,eps = 1e-18;
double Rand()
{
    return rand()%100000/10000.0;
}
void sol()
{
    double x1,y1,now;
    for(double t0 = 1067.18;t0>eps;t0*=d)
    {
        x1 = ax+t0*(rand()*2.0-RAND_MAX);
        y1 = ay+t0*(rand()*2.0-RAND_MAX);
        now = get_E(x1,y1);
        if(E-now>eps||exp((E-now)/t0)*RAND_MAX>rand())
        {
            E=now;
            ax=x1,ay=y1;
        }
    }
}
int main()
{
    srand(time(NULL));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w);
    E=get_E(0,0);
    int Time = 5;
    while(Time--)sol();
    printf("%.3lf %.3lf
",ax,ay);
    return 0;
}