bzoj 3680 吊打xxx 模拟退火

时间:2022-09-08 15:44:03

第一道模拟退火

重心嘛,就是要找到一个点,使其到所有点距离*该点权值和最小

思路:初始化一个T,mint,当T大于mint时,每次随机一个解,如果解比当前解优,直接转移,否则,以某概率(与T正相关)转移,并不断降温,最后向四周爬山

感觉思路比较清晰,但好多细节不太明白,比如初始化的T,mint,以及退火的速度,前后改了几十遍吧。还是要多做题,找感觉......

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 10050
using namespace std;
int n;
double minn=0x3f3f3f3f3f3f3f3fll;
struct point{
double x,y,g;
}p[N],ans;
double sqr(double x){return x*x;}
double dis(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
double Rand(){return (rand()%1000)/1000.0;}
double judge(point pp){
double ret=0;
for(int i=1;i<=n;i++)
ret+=p[i].g*dis(p[i],pp);
if(ret<minn){minn=ret;ans=pp;}
return ret;
}
void work(){
double T=1000000;
point now=ans;
while(T>0.001){
point nxt;
nxt.x=now.x+T*(Rand()*2-1);
nxt.y=now.y+T*(Rand()*2-1);
double dE= judge(now)-judge(nxt);
if((dE>0)||(exp(dE/T)>Rand())) now=nxt;
T*=0.97;
}
double nouse;
for(int i=1;i<=1000;i++){
point nxt;
nxt.x=ans.x+T*(Rand()*2-1);
nxt.y=ans.y+T*(Rand()*2-1);
nouse=judge(nxt);
}
}
int main(){
srand(20001101);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].g);
ans.x+=p[i].x; ans.y+=p[i].y;
}
ans.x/=n; ans.y/=n;
work();
printf("%0.3lf %0.3lf\n",ans.x,ans.y);
return 0;
}