Problem

https://www.luogu.org/problemnew/show/P1337

Solution

https://www.luogu.org/blog/peng-ym/solution-p1337

这里只是提下注意的几点：

1. 温度的变化量计入统计之中。$exp(-delta/T)$ 中的 delta 一定是正数。状态的扩展范围随温度的降低而降低。
2. 如果不保证初始答案很靠近正确答案的话，初始温度设高。退火温度大点倒是没什么关系。
3. 调特殊参有奇效。
4. 善用 RAND_MAX。

Code

// Code by ajcxsu
// Problem: balance_point

#include<bits/stdc++.h>
using namespace std;

const int N=1001;
double x[N], y[N], w[N];

int n;
double f(double nx, double ny) {
    double ret=0;
    for(int i=0;i<n;i++) ret+=sqrt((x[i]-nx)*(x[i]-nx)+(y[i]-ny)*(y[i]-ny))*w[i];
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>w[i];
    double ax=0, ay=0, nx, ny, T=19260817, delta=0.995, eps=1e-15;
    while(T>eps) {
        nx=ax+(rand()*2-RAND_MAX)*T;
        ny=ay+(rand()*2-RAND_MAX)*T;
        double r=f(nx, ny)-f(ax, ay);
        if(r<0) ax=nx, ay=ny;
        else if(exp(-r/T)*RAND_MAX>rand()) ax=nx, ay=ny;
        T*=delta;
    }
    cout.setf(ios::fixed), cout<<setprecision(3);
    cout<<ax<<' '<<ay<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1337.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆