模拟退火76pts求助,有注释
查看原帖
模拟退火76pts求助,有注释
247992
_Cloud_楼主2022/9/30 21:53
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
using namespace std;
const int N = 55;
const int INF = 1061109567;

int n, m, k;
int f[N][N], c[N], t[N];
int cas[N], len;
int ans = 1e9 + 5;
int r[N];
//r[i]:连边的编号,c[i]:给定的城堡,t[i]:编号为i的节点是否为城堡,f[i][j]:最短路

int Rand(int l, int r) {
	return l + rand() % (r - l + 1);
}

int calc() {//求解当前答案
	int res = 0;
	memset(t, 0, sizeof t);
	for (int i = 1; i <= k; i++) t[cas[i]] = true;
	for (int i = 1; i <= m; i++) t[c[i]] = true;
//	for (int i = 1; i <= n; i++) if (t[i]) printf("%d ", i); puts("");
	for (int i = 1; i <= n; i++) {
		if (t[i]) continue;
		int dis = INF;
		for (int j = 1; j <= n; j++) if (t[j]) dis = min(dis, f[i][j]);
		res = max(res, dis);
	}
//	if (now == 1) {
//		printf("%d\n", n);
//		for (int i = 1; i <= n; i++) if (t[i]) printf("%d ", i); puts("");
//	}
	ans = min(ans, res);
	return ans;
}

void SA() {//退火
	random_shuffle(cas + 1, cas + len + 1);
	int cur = calc();
	for (double T = 1e4; T > 1e-4; T *= 0.99) {
		cur = calc();
		int x = Rand(1, k), y = Rand(k + 1, len);//随机两个数交换
		swap(cas[x], cas[y]);
		int np = calc(), dt = np - cur;
		if (exp(-dt / T) < (double) rand() / RAND_MAX) swap(cas[x], cas[y]);
	}
}

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] = min(f[i][j], f[i][k] + f[k][j]);
	return;
}

int main() {
	srand(time(NULL));
	memset(f, 0x3f, sizeof f);
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &r[i]), r[i]++;
	for (int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);
		f[i][r[i]] = min(f[i][r[i]], x);
		f[r[i]][i] = min(f[r[i]][i], x);
	}
	for (int i = 1; i <= m; i++) scanf("%d", &c[i]), c[i]++, t[c[i]] = true;
	for (int i = 1; i <= n; i++) if (!t[i]) cas[++len] = i;
	Floyd();
	if (k >= len) { printf("%d\n", calc()); return 0; }
	while ((double)clock() / CLOCKS_PER_SEC <= 0.7) SA();
	printf("%d\n", ans);
	return 0; 
}
2022/9/30 21:53
加载中...