Solution

可以先做下 这题。

先考虑不包含环的情况，可以二分答案，题目就转换为对于给定的 $K$，已知选择了 $M$ 个点，再选择尽可能少的节点，使得所有点都被「覆盖」。

「覆盖」的定义为：存在一个被选择的点与这个节点的距离不大于 $K$。

考虑贪心 + dp，直到不得不选择时才选择。设 $f_i$ 表示 $i$ 子树内距离 $i$ 最远没被覆盖的点，$g_i$ 表示 $i$ 子树内距离 $i$ 最近被选择的点。

那么有：

$f_u=\max\limits_{v \in son_u}(f_v+dis_{v,u})$

$g_u=\min\limits_{v \in son_u}(g_v+dis_{v,u})$

接下来就是分类讨论，设二分的值为 $mid$：

1. $u$ 已经被选过了，有 $f_u=-inf,g_u=0$。
2. 若 $f_u+g_u\le mid$，说明离 $u$ 最远没被覆盖的点可以被覆盖到，$f_u=-inf$。
3. 若 $g_u > mid$，说明 $u$ 无法被 $u$ 子树内的点覆盖，那么 $f_u=\max(f_u,0)$。即若 $f_u > 0$，说明有子树有比它更深的未被覆盖的点，只需考虑比它深的点。若 $f_u<0$ 说明 $f_u$ 就是最深未被覆盖的点，$f_u=0$。
4. 若 $f_u+dis_{u,fa_u} > mid$，则如果 $u$ 不被选择，那么最深的那个点则再也无法被覆盖，$f_u=-inf,g_u=0$，选的点个数加 $1$。

但是它是一颗基环树，则可以考虑删除基环上的一条边，将其转换成一棵树，然后按上述过程处理即可即可。

注意：存在基环树森林，要将每棵树分开处理。

Code

#include<bits/stdc++.h>
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define ll long long
#define db double
#define pb push_back
#define eb emplace_back
#define MS(x,y) memset(x,y,sizeof x)
#define MC(x,y) memcpy(x,y,sizeof x)
#define PLL pair<ll,ll>
#define lb(x) (x&-x)
using namespace std;
const int N=50+5,M=1e5+5;
const ll INF=1ll<<60,mod=998244353;
int n,m,k,Tot,r[N],deg[N];
ll f[N],g[N],df[N],d[N];//df u 表示到 u 父亲的距离
vector<int> tr[N];//基环树森林，tr[i] 表示以 i 为根时子树的所有节点
bool cir[N],is[N],vis[N],ff[N];
//cir 表示是否在环上，is 表示是否已经被选择，ff 表示是否为一颗基环树的根
struct node{
	ll v,dis,id;//表示到的节点，距离，边的编号
};
vector<node> to[N];
void init(int u,int tf){
	vis[u]=1;tr[tf].pb(u);
	for(auto tp:to[u]) if(!vis[tp.v]) init(tp.v,tf);
}
void dfs(int u,int fa,int del,int mid){
    f[u]=-INF,g[u]=INF;
    for(auto tp:to[u]){
		int id=tp.id,v=tp.v,dis=tp.dis;
		if(v==fa || del==id) continue;
		df[v]=dis;
        dfs(v,u,del,mid);
		f[u]=max(f[v]+dis,f[u]);
		g[u]=min(g[v]+dis,g[u]);        
    }
	if(is[u]) f[u]=-INF,g[u]=0;
	if(f[u]+g[u]<=mid) f[u]=-INF;
	if(g[u]>mid) f[u]=max(f[u],0ll);
	if(f[u]+df[u]>mid) f[u]=-INF,g[u]=0,Tot++;    
}
int calc(int tf,int mid){
	if(!ff[tf]) return 0;//要满足 tf 为这颗基环树的根
	Tot=0;
    int Cnt=mod;
	for(int i:tr[tf]){//枚举删的边
		if(!cir[i]) continue;
		Tot=0;
        dfs(tf,0,i,mid);
		if(f[tf]>=0) Tot++;//根内存在未被覆盖的
		Cnt=min(Cnt,Tot);
	}
	return Cnt;
}
bool check(int mid){
	int tot=0;
	for(int i=1;i<=n;i++) tot+=calc(i,mid);
	return tot<=k;
}
void topo(){//拓扑求环，转换为 i->r[i] 的有向图，这个点如果在有向图的环上则在基环上
	queue<int> q;
	for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
		int u=q.front();q.pop();
		int v=r[u];
		if(--deg[v]==0) q.push(v);
	}
	for(int i=1;i<=n;i++) cir[i]=deg[i];
}
int main(){
	IOS;cin>>n>>m>>k;
    //转化为下标为 1 ~ n
	for(int i=1;i<=n;i++) cin>>r[i],r[i]++;
	for(int i=1;i<=n;i++) cin>>d[i];
	for(int i=1;i<=n;i++){
		to[i].pb({r[i],d[i],i}),to[r[i]].pb({i,d[i],i});//无向图
		deg[r[i]]++;
	}
	for(int i=1,x;i<=m;i++) cin>>x,is[++x]=1;
	topo();
	for(int i=1;i<=n;i++){
		if(!vis[i]) ff[i]=1,init(i,i);//遍历一整棵树，这棵基环树以 i 为根
	}
	int l=0,r=5e7;//二分答案
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<"\n";
	return 0;
}

本题解在阅读了 Phi_Quadrant 大佬的题解 后对其算法描述模糊之处进行了进一步解释。

模拟退火

模拟退火相较于爬山算法，无非就是有概率接受更劣解。对于相较于当前更优的解便无条件接受。而这个概率则是 $e^{\frac{-\Delta E}{T}}$。而 $T$ 值则是当前的温度。温度越高，我们的热情越高涨，便有较大的概率去接受更劣解。随着 $T$ 的渐渐冷却，我们的热情渐渐降低，不想再去接受更劣解，最后慢慢退化成了爬山算法。

算法过程

既然与距离有关，那么我们必然要建一个邻接矩阵存储边信息。之后跑一次 Floyd 得到两点之间的最短路径。之后将有城堡的城市编号放入数组 $a$ 中，并且标记一下。遍历 $1\to n$，对于当前元素，如果没有被标记，且数组 $a$ 的长度小于 $m+k$，即能够收到城堡的保护的城市，我们便将其也放在 $a$ 数组中，否则将其放入数组 $b$。

显然地，当 $k=0$ 时，就不用再跑模拟退火了，答案即为当前排列 $a,b$ 的 $\max (dist(c))$。其中 $dist(c)$ 为城市 $c$ 的最近城堡离它的距离。还有当 $m+k=n$ 时，答案必然为 $0$，因为全都是城堡了。

之后就要考虑如何将模拟退火套入本题了。我们引入温度参数 $T$ 和降温参数 $\alpha$。令 $T=10^9,\alpha=0.997$。在 $T$ 不断降温的同时我们不断取到随机数 $x,y$。交换 $a_x,b_y$。如果当前的 $\max (dist(c))$ 小于当前最优解，更新最优解。如果在概率之内但是是更劣解，也更新最优解。

引入卡时操作。

int ans = SA();
while((clock()-sta)*1.0/CLOCKS_PER_SEC<0.75) ans = min(ans, SA()); // 极品卡时，这道题限制 0.8s，我们卡 0.75s

这样便保证代码不会超时，注意的是要留个 $0.05s\to0.1s$，以免评测机浮动已经其他时间开销。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m, k, r[N], d, dis[N][N], x;
bool vis[N];
vector<int> a, b;
int check() { // 求从没有城堡保护的城市到有城堡保护的最近的城市的距离
	int ans = 0;
	for(int i=0; i<b.size(); i++) {
		int mina = 1e9;
		for(int j=0; j<a.size(); j++)
			mina = min(mina, dis[a[j]][b[i]]);
		ans = max(ans, mina); // 求 max{dist(c)}
	}
	return ans;
}
int Rand(int x) { // 瞎写一个随机数
	return ((1ull*rand()*rand()*1919180+rand()*114514)^rand())%x;
}
int SA() {
	double T = 1e9, alpha = 0.997;
	int now = check();
	if(k==0) return now; // 如果 k 的名额为 0，那么就是当前答案了
	if(m+k==n) return 0; // 如果全都是城堡就不用任何花费了
	while(T>1e-4) {
		int x = rand()%k+m, y = rand()%(n-m-k); // a.size() 为 k，b.size() 为 n-m-k，不越界的话随机数只能是这个
		swap(a[x], b[y]);
		int nxt = check();
		if(nxt<now||(nxt>=now&&Rand(10000000)<10000000*exp(-(nxt-now)/T))) now = nxt; // 在概率之内就选择接受更劣解
		else swap(a[x], b[y]);
		T *= alpha; // 降温
	}
	return now;
}
int main() {
	scanf("%d %d %d", &n, &m, &k);
	for(int i=1; i<=n; i++) scanf("%d", &r[i]);
	memset(dis, 0x3f, sizeof(dis));
	for(int i=1; i<=n; i++) {
		scanf("%d", &d); r[i]++; // 因为编号是 0~n-1，所以要加 1
		dis[i][r[i]] = dis[r[i]][i] = min(dis[i][r[i]], d);
		dis[i][i] = 0;
	}
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]); // Floyd 跑一遍最短路
	for(int i=1; i<=m; i++) {
		scanf("%d", &x); x++; // 因为编号是 0~n-1，所以要加 1
		a.push_back(x), vis[x] = 1;
	}
	for(int i=1; i<=n; i++) {
		if(!vis[i]) {
			if(a.size()<m+k) a.push_back(i); // a 是能够得到城堡保护的城市
			else b.push_back(i); // b 是不能够得到城堡保护的城市
		}
	}
	clock_t sta = clock();
	int ans = SA();
	while((clock()-sta)*1.0/CLOCKS_PER_SEC<0.75) ans = min(ans, SA()); // 极品卡时，这道题限制 0.8s，我们卡 0.75s
	printf("%d", ans);
    return 0;
}