bzoj 3680(洛谷1337) 吊打XXX—

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

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

模拟退火大概是从当前状态出发，随机一个状态（温度越高，这个状态与原状态越不同）；该状态比原状态优，则直接变成该状态，不然以概率（温度越高，概率越大）变成该状态；可以一边更新答案，更新答案就没概率一说，只往最优的方向更新，即刚才的概率是为了改变原状态使得可以通过该状态找到新的可能更优的状态。

弄这些和温度有关的概率可以这样：( rand()*2 - RAND_MAX ) * T 作为新状态对原状态的改变量；因为 T 最后会变成一个小数，所以即使前面是一个整型，最后也会变得很小；exp( delta/T ) 作为接受状态的概率，如果是值越大越差，则当值为正的时候，温度越高，该函数值越小，所以可以以 exp( delta/T )*RAND_MAX < rand() 作为判断。

本题最优化的是绳子长度×重量的和，越小说明越稳定。

bzoj上数据范围略大，精度低一点也能过，主要是不TLE；洛谷上数据小，但需要很高的精度。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define db double

using namespace std;

const int N=1e4+;

const db dc=0.997,eps=1e-;

int n,x[N],y[N],w[N];

db ans,px,py;

db gtrd(db T){return (rand()*-RAND_MAX)*T;}

db dis(db x0,db y0,db x1,db y1)

{

  return sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));

}

db calc(db nx,db ny)

{

  db ret=;

  for(int i=;i<=n;i++)ret+=dis(x[i],y[i],nx,ny)*w[i];

  return ret;

}

void SA(db T)

{

  db x0=gtrd(T),y0=gtrd(T),pr=calc(x0,y0),x,y,cr;

  while(T>eps)

    {

      x=x0+gtrd(T); y=y0+gtrd(T); cr=calc(x,y);

      if(cr<pr||exp((cr-pr)/T)*RAND_MAX<rand())

    {

      if(cr<ans)ans=cr,px=x,py=y;

      x0=x;y0=y;pr=cr;

    }

      T*=dc;

    }

}

int main()

{

  srand(time());

  scanf("%d",&n);

  for(int i=;i<=n;i++)

    scanf("%d%d%d",&x[i],&y[i],&w[i]),px+=x[i],py+=y[i];

  px/=n; py/=n; ans=calc(px,py);

  SA();SA();SA();

  printf("%.3lf %.3lf\n",px,py);

  return ;

}

巴特西

bzoj 3680(洛谷1337) 吊打XXX——模拟退火

最新文章

热门文章