洛谷 P1337 平衡点 & bzoj 3680 吊打 XXX —— 模拟退火

时间：2021-01-21 15:42:35

题目：https://www.luogu.org/problemnew/show/P1337

https://www.lydsy.com/JudgeOnline/problem.php?id=3680

模拟退火！其实就是随机移动产生解，而且幅度越来越小，以一定的概率接受不优的解；

设置一个“初温”，每次变小，作为移动的幅度和判断的系数之一；

exp 是以 e 为底的幂，这个判断依据似乎是个公式；

然后过程中保留一个最优解作为最后的答案；

洛谷那道题 n <= 1000，所以 eps 设了 1e-17，dt 设了 0.997，并且做了三次 SA (否则会WA)；

bzoj 的 n <= 10000，所以 eps 设了 1e-15，dt 设了 0.99，并且只做了一次 (否则会T)；

感觉设这些系数很需要经验呢，随机化算法嘛。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<ctime>

#include<cstdlib>

#include<cmath>

#define eps 1e-15//1e-17

#define dt 0.99//0.997

using namespace std;

typedef double db;

int const xn=;

int n,xx[xn],yy[xn],w[xn];

db ansx,ansy,ans;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

db dis(db x,db y,db a,db b){return sqrt((x-a)*(x-a)+(y-b)*(y-b));}

db cal(db x,db y)

{

  db sum=;

  for(int i=;i<=n;i++)sum+=dis(x,y,xx[i],yy[i])*w[i];

  return sum;

}

void SA()

{

  db T=,tx,ty,x=ansx,y=ansy,lst=ans;

  while(T>eps)

    {

      tx=x+(rand()*-RAND_MAX)*T;

      ty=y+(rand()*-RAND_MAX)*T;

      db tmp=cal(tx,ty),delt=tmp-lst;

      if(delt<||exp(delt/T)*RAND_MAX<rand())x=tx,y=ty,lst=tmp;

      if(tmp<ans)ans=tmp,ansx=tx,ansy=ty;

      T*=dt;

    }

}

int main()

{

  srand(time());

  n=rd(); int sx=,sy=;

  for(int i=;i<=n;i++)xx[i]=rd(),yy[i]=rd(),w[i]=rd(),sx+=xx[i],sy+=yy[i];

  ansx=1.0*sx/n; ansy=1.0*sy/n; ans=cal(ansx,ansy);

  SA();

  printf("%.3lf %.3lf\n",ansx,ansy);

  return ;

}

相关文章