求助模拟退火
  • 板块灌水区
  • 楼主slzx2021zjx
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/11/16 14:18
  • 上次更新2023/11/16 16:33:09
查看原帖
求助模拟退火
579035
slzx2021zjx楼主2023/11/16 14:18

P1337 45pts,是精度不够吗?

#include<bits/stdc++.h>
#define int long long
using namespace std;
double ansx,ansy,ans=1e8,T,delta=0.996;
int n;
struct str{
	int x,y,w;
}a[1005];
double calc(double x,double y){
	double tmp=0;
	for(int i=1;i<=n;i++){
		double delx=x-a[i].x,dely=y-a[i].y;
		tmp+=sqrt(delx*delx+dely*dely)*a[i].w;
	}
	return tmp;
} 
void simulate_anneal(){
	double x=ansx,y=ansy;
	T=2000;
	while(T>1e-14){
		double xx=x+((rand()<<1)-RAND_MAX)*T;
		double yy=y+((rand()<<1)-RAND_MAX)*T;
		double anss=calc(xx,yy);
		double DELTA=anss-ans;
		if(DELTA<0){
			x=xx,y=yy;
			ansx=xx,ansy=yy,ans=anss;
		}
		else if(exp(-DELTA/T)*RAND_MAX>rand()) x=xx,y=yy;
		T*=delta;
	}
}
void Solve(double sx,double sy){
	ansx=(double)sx/n,ansy=(double)sy/n;
	simulate_anneal();
	srand(rand());
	simulate_anneal();
	srand(rand());
	simulate_anneal();
}
signed main()
{
	srand('xyymyj');
	scanf("%lld",&n);
	double sx=0,sy=0;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);
		sx+=a[i].x,sy+=a[i].y;
	}
	Solve(sx,sy);
	printf("%.3f %.3f\n",ansx,ansy);
}
2023/11/16 14:18
加载中...