1239 - [SCOI2008]城堡castle

题解bymod998244353

模拟退火枚举k个没有城堡的城市，建立城堡+dijkstra

#include<bits/stdc++.h>
using namespace std;
const int MAXN=64;
int n,m,k;
struct Edge {
	int v,w,next;
} edge[MAXN<<1];
int head[MAXN],ecnt;
void addedge(int u,int v,int w) {
	edge[++ecnt].v=v;
	edge[ecnt].w=w;
	edge[ecnt].next=head[u];
	head[u]=ecnt;
}
int t1[MAXN],ans,t2[MAXN],to[MAXN],cnt,dis[MAXN];
bool vis[MAXN];
priority_queue<pair<int,int> >q;
void dijkstra() {
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	while(!q.empty())q.pop();
	for(int i=1; i<=m; ++i) q.push(make_pair(dis[t1[i]]=0,t1[i]));
	for(int i=1; i<=k; ++i) q.push(make_pair(dis[t2[i]]=0,t2[i]));
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u],v,w; i; i=edge[i].next) {
			v=edge[i].v;
			w=edge[i].w+dis[u];
			if(w<dis[v]) {
				dis[v]=w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}
int calc() {
	int maxn=0;
	dijkstra();
	for(int i=1; i<=n; ++i)maxn=max(maxn,dis[i]);
	return maxn;
}
void sa() {
	for(double t=3000; t>=1e-14; t*=0.996) {
		int x=rand()%k+1,y=rand()%(cnt-k)+1+k;
		swap(t2[x],t2[y]);
		int tmp=calc(),de=tmp-ans;
		if(de<0) {
			ans=tmp;
		} else if(exp(-de/t)*RAND_MAX<=rand()) {
			swap(t2[x],t2[y]);
		}
	}
}
int main() {
	srand(20070225);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&to[i]);
		++to[i];
	}
	for(int i=1,d; i<=n; ++i) {
		scanf("%d",&d);
		addedge(i,to[i],d);
		addedge(to[i],i,d);
	}
	for(int i=1; i<=m; ++i) {
		scanf("%d",&t1[i]);
		++t1[i];
		vis[t1[i]]=true;
	}
	for(int i=1; i<=n; ++i) {
		if(!vis[i]) {
			t2[++cnt]=i;
		}
	}
	ans=calc();
	if(n>m+k) {
		do sa();
		while((double)clock()/CLOCKS_PER_SEC<=0.6);
	}
	printf("%d\n",ans);
	return 0;
}