模拟退火（Simulate Anneal）是一种通用概率演算法，在大的搜索空间内寻找最优解，若新的状态优于当前状态，则将新的状态作为最优解，否则以一定概率接受新的状态。
模拟退火有三个因数，初始温度T0，降温系数d，终止温度Tk，通常不直接取当前解为最优解，而是维护退火过程中遇到的所有解的最优值。
inline void SimulateAnneal(){
double t=3000;/*初始温度*/
while(t>1e-15){/*尚未达到终止温度，可以用时间代替*/
double nx=ansx+(rand()*2-RAND_MAX)*t,ny=ansy+(rand()*2-RAND_MAX)*t/*下一个点的坐标*/,re=calc(nx,ny)/*下一个点的答案*/,delta=re-ans;/*两点答案的差值*/
if(delta<0){/*下一个点比当前点更优*/
ansx=nx;
ansy=ny;
ans=re;
}
else if(exp(-delta/t)*RAND_MAX>rand()){/*以多项式概率接受下一个点的坐标*/
ansx=nx;
ansy=ny;
}
t*=0.97;/*逐步降温*/
}
}
求n个点的带权类费马点。首先选定一个答案点并计算，之后挑选根据温度跳出一段距离，比较那个点的答案并决定是更新答案还是以一定概率接受坐标。
inline double calc(double a,double b){
double re=0;
for(int i=1;i<=n;i++){
double dx=x[i]-a,dy=y[i]-b;
re+=sqrt(dx*dx+dy*dy)*w[i];
}
return re;
}
inline void SimulateAnneal(){
double t=3000;
while(t>1e-15){
double nx=ansx+(rand()*2-RAND_MAX)*t,ny=ansy+(rand()*2-RAND_MAX)*t,re=calc(nx,ny),delta=re-ans;
if(delta<0){
ansx=nx;
ansy=ny;
ans=re;
}
else if(exp(-delta/t)*RAND_MAX>rand()){
ansx=nx;
ansy=ny;
}
t*=0.97;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d%d",x+i,y+i,w+i),ansx+=x[i],ansy+=y[i];
ansx/=n;
ansy/=n;
ans=calc(ansx,ansy);
for(int i=1;i<=3;i++)SimulateAnneal();
printf("%.3lf %.3lf\n",ansx,ansy);
return 0;
}
每头牛有三个朋友，求一个排列使得每对朋友之间的距离和最小。首先列出一个排列并计算答案，每次降温时选出两头牛并交换它们的位置，注意要去重。
inline int calc(){
int re=0;
for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)re+=abs(pos[i]-pos[f[i][j]]);
return re;
}
inline void SimulateAnneal(){
double t=3000;
while(t>1e-15){
int x=rand()%n+1,y=rand()%n+1;
while(x==y)x=rand()%n+1,y=rand()%n+1;
swap(pos[x],pos[y]);
int re=calc(),delta=re-ans;
if(delta<0)ans=re;
else if(exp(-delta/t)*RAND_MAX<rand())swap(pos[x],pos[y]);
t*=0.97;
}
}
将n个数分为m组，计算每组的和，求这m个数的最小方差。对于给定序列，为了让方差最小，需要在加入数时加入当前和最小的一组，降温时随机交换两个数。
inline double calc(){
double re=0,tmp[N];
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n;i++){
int p=1;
for(int j=1;j<=m;j++)if(tmp[j]<tmp[p])p=j;
tmp[p]+=be[i];
}
for(int i=1;i<=m;i++)re+=(tmp[i]-ave)*(tmp[i]-ave);
return sqrt(1.0*re/m);
}
inline void SimulateAnneal(){
double t=10000;
for(int i=1;i<=n;i++)be[i]=bl[i];
while(t>1e-15){
int x=rand()%n+1,y=rand()%n+1;
while(x==y)x=rand()%n+1,y=rand()%n+1;
swap(be[x],be[y]);
double re=calc(),delta=re-ans;
if(delta<0){
ans=re;
for(int i=1;i<=n;i++)bl[i]=be[i];
}
else if(exp(-delta/t)<rand())swap(be[x],be[y]);
t*=0.97;
}
}
for(int i=1;i<=n;i++)scanf("%d",a+i),be[i]=bl[i]=a[i],ave+=a[i];
ave/=m;
给出n+1个点，求一个n维球的球心坐标。初始答案点为所有点坐标和的平均值，之后计算每个维度和其他点的距离并求平均值，根据平均值计算差值，结合温度进行爬山。
inline double dist(const node&a,const node&b){
double re=0;
for(int i=1;i<=n;i++)re+=(a.a[i]-b.a[i])*(a.a[i]-b.a[i]);
return sqrt(re);
}
inline void SimulateAnneal(){
double t=10000;
while(t>0.0001){
double ave=0;
for(int i=1;i<=n+1;i++)dis[i]=dist(ans,p[i]),ave+=dis[i];
ave/=n+1;
for(int i=1;i<=n;i++)delta.a[i]=0;
for(int i=1;i<=n+1;i++)for(int j=1;j<=n;j++)delta.a[j]+=(dis[i]-ave)*(p[i].a[j]-ans.a[j])/ave;
for(int i=1;i<=n;i++)ans.a[i]+=delta.a[i]*t;
t*=0.99999;
}
}
for(int i=1;i<=n+1;i++)for(int j=1;j<=n;j++)scanf("%lf",(p+i)->a+j),ans.a[j]+=p[i].a[j]/(n+1);
n个城市m个堡垒，可以使k个城市成为堡垒，dis(x)表示距离城市x到最近的堡垒的距离，求max(dis(i))的最小值。每次降温时暴力求最短路，随机已选的一个点和可选但是未选的点进行交换，注意当可以全部成为堡垒时要特判。
inline void spfa(){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
for(int i=1;i<=m;i++)dis[pos[i]]=0,q.push(pos[i]);
for(int i=1;i<=k;i++)dis[can[i]]=0,q.push(can[i]);
while(!q.empty()){
int x=q.front();
q.pop();
in[x]=false;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
if(in[y]==false){
in[y]=true;
q.push(y);
}
}
}
}
}
inline int calc(){
spfa();
int re=0;
for(int i=1;i<=n;i++)re=max(re,dis[i]);
return re;
}
inline void SimulateAnneal(){
double t=3000;
while(t>1e-15){
int x=rand()%k+1,y=rand()%(can[0]-k)+1;
swap(can[x],can[k+y]);
int re=calc(),delta=re-ans;
if(delta<0)ans=re;
else if(exp(-delta/t)*RAND_MAX<=rand())swap(can[x],can[k+y]);
t*=0.997;
}
}
}
for(int i=1;i<=m;i++)cin>>pos[i],in[++pos[i]]=true;
for(int i=1;i<=n;i++)if(in[i]==false)can[++can[0]]=i;
将一个序列分成两组且数量插值不超过1，求两组和的差值的最小值。排序后进行分组，随即交换两组中的数，注意特判只有一组的情况。
inline int calc(){
int re=0;
for(int i=1;i<=b[0];i++)re+=b[i];
for(int i=1;i<=c[0];i++)re-=c[i];
return abs(re);
}
inline void SimulateAnneal(){
double t=3000;
while(t>1e-15){
int x=rand()%b[0]+1,y=rand()%c[0]+1;
swap(b[x],c[y]);
int re=calc(),delta=re-ans;
if(delta<0)ans=re;
else if(exp(-delta/t)*RAND_MAX<=rand())swap(b[x],c[y]);
t*=0.999;
}
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
if(i&1)b[++b[0]]=a[i];
else c[++c[0]]=a[i];
}
ans=calc();
if(b[0]==0||c[0]==0){
cout<<ans<<'\n';
continue;
}