玄学调参。
反正我是挂在\(52\)分。
随机化果然不要想满分啊。
放个代码好了。
[SCOI2008]城堡
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#define ll long long
#define N 600
ll n,m,k,to[N],f[N][N],p[N],can[N];
inline void floyd(){
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] = std::min(f[i][j],f[i][k] + f[k][j]);
}
inline ll find(){
ll ans = 0;
for(int i = 1;i <= n;++i){
ll tans = 0x7f7f7f7f;
if(p[i])
continue;
for(int j = 1;j <= n;++j)
if(p[j])
tans = std::min(tans,f[i][j]);
// std::cout<<i<<" "<<tans<<std::endl;
ans = std::max(ans,tans);
}
return ans;
}
ll fans = 0x7f7f7f7f;
inline void SA(){
double T = 5000;
double eps = 1e-10;
while(T >= eps){
ll x,y;
x = rand() % can[0] + 1;y = rand() % can[0] + 1;
ll z = -find();
std::swap(p[can[x]],p[can[y]]);
ll w = find();
z += w;
if(z < 0)
fans = std::min(fans,w);
if(z >= 0 && exp(-z / T) * RAND_MAX <= rand())
std::swap(p[can[x]],p[can[y]]);
T *= 0.993;
}
}
int main(){
srand(3491062232);
std::memset(f,0x3f,sizeof(f));
scanf("%lld%lld%lld",&n,&m,&k);
for(int i = 1;i <= n;++i)
scanf("%lld",&to[i]),to[i] ++ ;
for(int i = 1;i <= n;++i){
ll x;
scanf("%lld",&x);
f[to[i]][i] = f[i][to[i]] = std::min(f[i][to[i]],x);
}
floyd();
for(int i = 1;i <= m;++i){
ll x;
scanf("%lld",&x);
p[x] = 1;
}
for(int i = 1;i <= n;++i){
if(!p[i])
can[++can[0]] = i;
}
ll ki = k;
for(int i = 1;i <= n,ki;++i){
if(!p[i])
p[i] = 1,ki -- ;
}
fans = find();
if(m + k == n)
std::cout<<fans<<std::endl;
else{
while(((double)(clock())/CLOCKS_PER_SEC)<0.6)
SA();
std::cout<<fans<<std::endl;
}
}