52分退火模拟
查看原帖
52分退火模拟
226944
光锥xn楼主2021/4/18 23:44
#include<bits/stdc++.h>
#define delta 0.995
#define ma 55
using namespace std;
int n,m,k,r[ma],d[ma];
int f[ma][ma],emp[ma],tot,ans=1e9;//emp 武城可选 
bool mc[ma],vis[ma];//mc 是否有城 
void dis()
{
	int i,j,k;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int calc()
{
	int i,j,minn,s=0;
	for(i=1;i<=n;i++)
		if(!mc[i]){
			minn=1e9;
			for(j=1;j<=n;j++)if(mc[j])minn=min(minn,f[i][j]);
			s=max(s,minn);
		}
	return s;
}
void fire()
{
	double t=3000;
	while(t>=1e-15)
	{
		int x,y,na,de;
		x=rand()%k+1;
		y=rand()%(tot-k)+k+1;
		swap(mc[emp[x]],mc[emp[y]]);
		na=calc();
		de=na-ans;
		if(de<0)ans=na;
		else if(exp(-de/t)*RAND_MAX<=rand())swap(mc[emp[x]],mc[emp[y]]);
		t*=delta; 
	}
}
void sa()
{
	fire();
	fire();
	fire();
	fire();
}
int main()
{	
	register int cnt,i,x;
	scanf("%d%d%d",&n,&m,&k);srand(23333);
	memset(f,0x3f,sizeof(f));
	for(i=1;i<=n;i++)scanf("%d",&r[i]),++r[i];
	for(i=1;i<=n;i++)scanf("%d",&d[i]);
	for(i=1;i<=n;i++)
		f[i][r[i]]=min(f[i][r[i]],d[i]),f[r[i]][i]=min(f[r[i]][i],d[i]);
	for(i=1;i<=n;i++)f[i][i]=0;
	dis();
	for(i=1;i<=m;i++){
		scanf("%d",&x);
		mc[++x]=1,vis[x]=1;
	}
	for(i=1;i<=n;i++)if(!vis[i])emp[++tot]=i;
	for(cnt=1,i=1;cnt<=k&&i<=n;i++,cnt++)if(!mc[i])mc[i]=1;
	ans=calc();
	if(m+k==n){printf("0");return 0;}
	sa();
	printf("%d",ans);
}

看了又看,没查出来,求大佬

2021/4/18 23:44
加载中...