首页 > > 程序设计 > C/C++ >

POJA Star not a Tree?(模拟退火)

2018-09-18 06:25:15来源：博客园阅读 ()

题意

题目链接

给出$n$个点，求出一个点使得到各个点的距离之和最小，距离为欧几里得距离

Sol

模拟退火真是玄学，我退了一上午，最后把exp函数去了就A了。

后来改了改，发现是大小符号的问题。。

但是

这样是对的。

然后把RAND_MAX除过去就错了。。

需要改大小号才行。真是玄学。。。

/*
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
const int MAXN = 1e5 + 10;
const double eps = 1e-10, Dlt = 0.97;
int N;
double xx[MAXN], yy[MAXN];
double Ans;
double rand(double T, int opt) {
    return opt * T ;
}
double sqr(double x) {
    return x * x;
}
double calc(double x, double y) {
    double ans = 0;
    for(int i = 1;i <= N; i++)
        ans += sqrt(sqr(x - xx[i]) + sqr(y - yy[i]));
    return ans;
}
void solve(double x, double y) {
    double now = calc(x, y);
    Ans = min(Ans, now);
    for(double T = 10000; T > eps; T *= Dlt) {
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                double wx = x + rand(T, i), wy = y + rand(T, j);
            //    if(wx < 0 || wy < 0 || wx > 10000 || wy > 10000) continue;
                double wv = calc(wx, wy);
            //    printf("%lf %lf %lf\n", wx, wy, calc(wx, wy));
                if(wv < Ans) x = wx, y = wy, Ans= wv;
                if(wv < now || ( exp((now - wv) / T) < (rand() / RAND_MAX) )) x = wx, y = wy, now = wv;    
            //    if(wv < now) x = wx, y = wy, now = wv;                    
            }
        }
    }
}
int main() {
    srand(19260817);
//    freopen("a.in", "r", stdin);
    Ans = 1e20;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%lf %lf", &xx[i], &yy[i]);
    //printf("%lf", calc(5000, 5000));
    //for(int i = 1; i <= N; i++) {
    //    double x = rand() % 10000, y = rand() % 10000;
        solve(xx[2], yy[2]);
    //}
    printf("%d", (int)(Ans + 0.5));
    return 0;
}
/*
4
0 0
0 5000
2354 10000
8787 0
*/