题解：P2538 [SCOI2008] 城堡

· · 题解

本题解在阅读了 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;
}