题解：P2210 Haywire

LostKeyToReach · 2024-08-12 09:08:57 · 题解

我爱随机化算法！

对于这道题，我们考虑使用模拟退火。我们将初始温度设为 25，每次温度乘上 0.99。对于每次操作，我们把 1 \sim n 的一个排列打乱一次，然后计算答案并且更新即可。

为了防止答案错误，我们可以卡时或者限定运行次数（3000 次就够了），足以通过本题。

参考代码如下：

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define debug(x) cerr << (#x) << '\n'
#define ls (u << 1)
#define rs (u << 1 | 1)
#define pii pair <int, int>
#define pb emplace_back
#define chkmin(x, y) x > y ? x = y : 0
#define chkmax(x, y) x < y ? x = y : 0
#define L(i, a, b) for (int i = (a); i <= (b); i++)
#define R(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
const double eps = 1e-10;
const double dt = 0.99;
const int N = 1e5 + 6;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define rd(n) uniform_int_distribution <int>(1, n)(rnd)
#define rddb(n) uniform_real_distribution <double>(1, n)(rnd)
int n;
int a[14][4], p[14], ans = 0x3f3f3f3f;
int cal() {
    int ans = 0;
    L(i, 1, n) {
        L(j, 1, 3) {
            ans += abs(p[i] - p[a[i][j]]);
        }
    }
    return ans;
}
void SA() {
    double temp = 25.0;
    for (; temp >= eps; temp *= dt) {
        int x = rd(n), y = rd(n);
        swap(p[x], p[y]);
        int now = cal();
        if (now < ans) ans = now;
        else if (exp(abs(now - ans)) * 1.0 / temp < rddb(10000) / 32767) {
            ans = now;
        }
    }
}
signed main() {
    cin >> n;
    L(i, 1, n) {
        cin >> a[i][1] >> a[i][2] >> a[i][3];
        p[i] = i;
    }
    int t = 3000;
    while (t--) SA();
    cout << ans / 2;
}