[72,80]pst,悬关求调
查看原帖
[72,80]pst,悬关求调
537914
Zhao_zzZ楼主2024/11/8 14:18

rt

#include <bits/stdc++.h>
#define db double
using namespace std;
mt19937 rd(time(0));
const int N=50+10;
const int Inf=1e9;
int n,m,k,r[N],d[N],f[N][N],ans=Inf,a[N],tot;
bool st[N];
db timi() {return (db)clock()/CLOCKS_PER_SEC;}
db Rand() {return (db)(rd()%100000)/100000;}
int randd(int l,int r) {return rd()%(r-l+1)+l;}
void init(){
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int work(){
	int maxx=-1;
	for(int i=m+k+1;i<=n;i++){
		int minn=Inf;
		for(int j=1;j<=m+k;j++)
			minn=min(minn,f[a[i]][a[j]]);
		maxx=max(maxx,minn);
	}
//	if(ans>maxx){
//		for(int i=1;i<=m+k;i++) printf("%d ",a[i]);
//		printf("\n");
//		printf("ans=%d\n",maxx);
//	}
	ans=min(ans,maxx);
	return maxx;
}
void SA(){
	db T=1e5;
	db now=ans;
	while(T>1e-15){
		int x=randd(m+1,n-1);
		int y=randd(x+1,n);
		swap(a[x],a[y]);
		db nx=work();
		if(nx<now||exp((now-nw)/T)<Rand()) now=nx;
		else swap(a[x],a[y]);
		T*=0.9993;
	}
}
int main(){
//	freopen("H.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	if(m+k>=n){
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=n;i++) scanf("%d",&r[i]),++r[i];
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=Inf;
	for(int 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]);
	}
	init();
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);++x;
		st[x]=1;
		a[++tot]=x;
	}
	for(int i=1;i<=n;i++){
		if(st[i]) continue;
		a[++tot]=i;
	}
	while(timi()<0.75){
		SA();
	}
	printf("%d\n",ans);
	return 0;
}
2024/11/8 14:18
加载中...