专栏文章

题解：P2538 [SCOI2008] 城堡

SScentip
P2538题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minh66fl
此快照首次捕获于
2025/12/02 02:20
3 个月前
此快照最后确认于
2025/12/02 02:20
3 个月前
查看原文
本题解在阅读了 Phi_Quadrant 大佬的题解 后对其算法描述模糊之处进行了进一步解释。

模拟退火

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

算法过程

既然与距离有关，那么我们必然要建一个邻接矩阵存储边信息。之后跑一次 Floyd 得到两点之间的最短路径。之后将有城堡的城市编号放入数组 aa 中，并且标记一下。遍历 1→n1\to n，对于当前元素，如果没有被标记，且数组 aa 的长度小于 m+km+k，即能够收到城堡的保护的城市，我们便将其也放在 aa 数组中，否则将其放入数组 bb。
显然地，当 k=0k=0 时，就不用再跑模拟退火了，答案即为当前排列 a,ba,b 的 max⁡(dist(c))\max (dist(c))。其中 dist(c)dist(c) 为城市 cc 的最近城堡离它的距离。还有当 m+k=nm+k=n 时，答案必然为 00，因为全都是城堡了。
之后就要考虑如何将模拟退火套入本题了。我们引入温度参数 TT 和降温参数 α\alpha。令 T=109,α=0.997T=10^9,\alpha=0.997。在 TT 不断降温的同时我们不断取到随机数 x,yx,y。交换 ax,bya_x,b_y。如果当前的 max⁡(dist(c))\max (dist(c)) 小于当前最优解，更新最优解。如果在概率之内但是是更劣解，也更新最优解。
引入卡时操作。
C
int ans = SA();
while((clock()-sta)*1.0/CLOCKS_PER_SEC<0.75) ans = min(ans, SA()); // 极品卡时，这道题限制 0.8s，我们卡 0.75s
这样便保证代码不会超时，注意的是要留个 0.05s→0.1s0.05s\to0.1s，以免评测机浮动已经其他时间开销。

代码

C
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...