关于模拟退火
  • 板块P2210 Haywire
  • 楼主Jerry_heng
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/25 14:27
  • 上次更新2024/3/25 17:55:59
查看原帖
关于模拟退火
763878
Jerry_heng楼主2024/3/25 14:27

如果你样例一直没过,但找不出代码问题,一定要自信提交,比如这个代码(对着第一篇题解调了很久)。

#include<bits/stdc++.h>
using namespace std;
const double be=1e7,en=1e-16;
int f[21][4],n,pos[21],pp[21];
int Rand(int l,int r){
	return rand()%(r-l+1)+l;
}
int solve(){
	int sum=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=3;j++)
			sum+=abs(pp[i]-pp[f[i][j]]);
	return sum;
}
int main(){
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=3;j++)
			scanf("%d",&f[i][j]);
		pos[i]=i;
		pp[i]=i;
	}
	int res=solve();
	while((clock()/(1.0*CLOCKS_PER_SEC))<=0.9){
		int ne=res;
		for(int i=1;i<=n;i++)pp[i]=pos[i];
		for(double i=be;i>=en;i*=0.99){
			int x,y;
			do{
				x=Rand(1,n);
				y=Rand(1,n);
			}while(x==y);
			swap(pp[x],pp[y]);
			ne=solve();
			if(ne<=res)res=ne;
			else if((1.0*exp(res-ne))/i>(1.0*rand()/RAND_MAX)){
				swap(pp[x],pp[y]);
			}
		}
	}
	printf("%d\n",res/2);
	return 0;
}
2024/3/25 14:27
加载中...