网上和洛谷绝大部分讲解模拟退火的实现都是错误的……这里给出我的写法,如有错误还请指正。
其实是希望白嫖巨佬帮我检查
Statement
给定一个二维平面和 $N$ 个圆表示建筑,$M$ 个点表示敌人。可以任意放置一个半径任意的圆,使得覆盖尽可能多的敌人,且不会损伤建筑。
Solution
注意到,如果将问题转化成一个判定性的问题,即给定一个圆,判断覆盖了多少个点以及有没有损伤建筑。也就是说,checker
是很好写的。
那么我们可以使用随机化算法来解决这个问题,多次执行以及调试参数之后能达到很高的正确率。
Code
//Author:RingweEH
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
#define ll long long
#define db double
using namespace std;
int min( int a,int b ) { return (a<b) ? a : b; }
int max( int a,int b ) { return (a>b) ? a : b; }
void bmin( int &a,int b ) { a=(a<b) ? a : b; }
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
int read()
{
int x=0,w=1; char ch=getchar();
while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
while ( ch<='9' && ch>='0' ) { x=x*10+ch-'0'; ch=getchar(); }
return x*w;
}
const int N=11,M=1010;
const double delta=0.996,Te=1e-10; //D和最终温度
int n,m,x[N],y[N],r[N],p[M],q[M],R,ansout=0;
double ansx,ansy;
double dis( double ax,double ay,double bx,double by ) //求两点间距离
{
double res=(bx-ax)*(bx-ax)+(by-ay)*(by-ay);
res=sqrt(res);
return res;
}
int calc( double xx,double yy ) //估价函数
{
double nowr=R;
for ( int i=1; i<=n; i++ )
nowr=min( nowr,dis(xx,yy,x[i],y[i])-(double)r[i] );
int cnt=0;
for ( int i=1; i<=m; i++ )
if ( dis(xx,yy,p[i],q[i])<=nowr ) cnt++;
return cnt;
}
void SA()
{
double T=6000; //初始温度
int ans=0;
while ( T>Te )
{
double nowx=ansx+(rand()*2-RAND_MAX)*T;
double nowy=ansy+(rand()*2-RAND_MAX)*T;
int nowans=calc( nowx,nowy );
int DelE=nowans-ans;
if ( DelE>0 ) ansx=nowx,ansy=nowy,ans=nowans,ansout=max( ansout,ans );
//更优的解,必然接受
else if ( exp(DelE/sqrt(T))>(double)rand()/1215 ) ansx=nowx,ansy=nowy,ans=nowans;
//按概率接受,保证了越到后期,和最优解的差距越大,越难被接受
T*=delta;
}
}
int main()
{
srand(time(0)); ansx=ansy=0;
n=read(); m=read(); R=read();
for ( int i=1; i<=n; i++ )
x[i]=read(),y[i]=read(),r[i]=read();
for ( int i=1; i<=m; i++ )
p[i]=read(),q[i]=read(),ansx+=x[i],ansy+=y[i];
ansx/=m; ansy/=m; ansout=calc( ansx,ansy );
while ( (double)clock()/CLOCKS_PER_SEC<=0.85 ) SA();
printf( "%d",ansout );
}
%%% ,网上 、洛谷,大多数是模拟退火写错了,退化写成了爬山法。$rp$ 够的话,光爬山法就可以A过去了。洛谷的数据感觉好过一点,一发就能过。 这个构造 $exp(DelE/sqrt(T))>(double)rand()/1215$是 用数据慢慢 估出来的,还是其他方法,希望可以讲一下。
先赞后看,已成习惯
我虽然不知道,巨巨您是不是对得,但是我知道,点赞再看,QAQ!
QWQ
好习惯这习惯我i了