题面在这里
题意
...见链接吧
sol
在此发一篇模拟退火的题解
不得不说luogu的数据真是太良心啦
一句话解释模拟退火:在一个慢慢缩小的范围内随机状态寻找最优解，当转移状态更优时直接接受，当当前状态更优时以一定概率\((exp(dlt/T))\)接受
具体实现请参照代码
#include<bits/stdc++.h>#include<algorithm>#include<iostream>#include<cstdlib>#include<iomanip>#include<cstring>#include<vector>#include<cstdio>#include<string>#include<bitset>#include<cmath>#include<queue>#include<stack>#include<map>#include<set>#define sqr(x) ((x)*(x))#define pb push_back#define RG register#define il inlineusing namespace std;const int mod=1e9+7;const int N=1010;typedef unsigned long long ull;typedef vector<int>VI;typedef long long ll;typedef double dd;il ll read(){ ???RG ll data=0,w=1;RG char ch=getchar(); ???while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar(); ???if(ch==‘-‘)w=-1,ch=getchar(); ???while(ch<=‘9‘&&ch>=‘0‘)data=data*10+ch-48,ch=getchar(); ???return data*w;}int n;dd mn;struct point{dd x,y,w;}p[N],ans,now;il dd make(){return rand()%100000/100000.00;}il dd dis(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}il dd calc(point x){ ???RG dd ret=0; ???for(RG int i=1;i<=n;i++) ???????ret+=p[i].w*dis(x,p[i]); ???return ret;}il void SA(point x){ ???RG dd T=1e6; ???while(T>1e-3){//退火过程 ???????now.x=ans.x+T*(2*make()-1); ???????now.y=ans.y+T*(2*make()-1); ???????double dlt=calc(ans)-calc(now); ???????if(dlt>0||exp(dlt/T)>make())ans=now; ???????T*=0.996; ???} ???for(int i=1;i<=50000;++i)//最后在一定范围内搜寻到局部最优解 ???{ ???????now.x=ans.x+T*(2*make()-1); ???????now.y=ans.y+T*(2*make()-1); ???????if(calc(ans)-calc(now)>0)ans=now; ???}}int main(){ ???srand(time(NULL)+rand()); ???n=read(); ???for(RG int i=1;i<=n;i++) ???????scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w); ???ans=(point){make(),make(),0};mn=ans.w=calc(ans); ???SA(ans); ????printf("%.3lf %.3lf\n",ans.x,ans.y); ???return 0;}考试骗分，模拟退火，你值得拥有！