模拟退火

模拟退火是一种随机化算法，可以用来求解某些数据范围较小的最优化问题。由于其通常不能保证正确性，因此一般在数据量非常小或者题目允许输出近似值时才使用。

假如我们要最小化一个多元函数 \(f(s)\) 的值。我们先选择一个初始状态 \(s=s_0\)。模拟退火就是根据某些规则转移 \(s\)，直到其收敛到最优解附近。

其规则具体如下：

• 初始时有一个变量 \(T\) 表示当前温度；
• 若 \(T\ge lim\)：
• 随机转移到 \(s\) 附近的一个新状态 \(s'\)，计算 \(f(s')\)；
• 如果 \(f(s')\le f(s)\)，则直接转移：\(s\leftarrow s'\)；
• 否则，以 \(p=\exp(-\frac{f(s')-f(s)}T)\) 的概率转移：\(s\leftarrow s'\)；
• 否则，不进行转移；
• \(T'\leftarrow T\times stp\)；

\(stp\) 一般取 \(0.99999\)，\(lim\) 取 \(10^{-15}\)，\(T\) 和转移代价有关，一般 \(\ge 5\)。

• 找到高效计算 \(f(s)\) 的算法可以减少单次转移的时间消耗，提高退火次数；
• \((1-stp)\) 一般不小于 \(10^{-5}\)，否则会超时；
• 提取关键影响 \(f\) 值的信息，缩短初始状态和最优解之间的距离，也可以更准确的找到最优解；

选择合适的状态和转移，剩下的就是套板子。

P2210 Haywire

代码

#include<iostream>
#include<ctime>
#include<random>
#define ld double
#define ull unsigned long long
using namespace std;
const int N = 15;
const int INF = 0x3f3f3f3f;
const ull V = 0xffffffffffffffff;

mt19937_64 rng(clock());

int n, cur, ans;
int fri[N][3];

int s[N], ns[N];

int calc(int *a) {
    int res = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 3; j++) res += max(0, a[i] - a[fri[i][j]]);
    }
    return res;
}

inline int dist_int() { return rng() % n + 1; }
inline ld dist_ld() { return (ld)rng() / V; }

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> fri[i][0] >> fri[i][1] >> fri[i][2];

    for(int i = 1; i <= n; i++) s[i] = i;
    cur = calc(s);

    ans = INF;

    // 其实不卡时也能过
    ull bg = clock();
    while(3 * (clock() - bg) <= CLOCKS_PER_SEC) {
        ld T = 2000, lim = 1e-3, d = 0.999;
        while(T > lim) {
            for(int i = 1; i <= n; i++) ns[i] = s[i];
            int x = dist_int(), y = dist_int();
            while(y == x) y = dist_int();
            swap(ns[x], ns[y]);
            int tmp = calc(ns);
            bool flag = 0;
            if(tmp < cur) flag = 1;
            else if(dist_ld() <= exp(-(tmp - cur) / T)) flag = 1;
            if(flag) {
                cur = tmp;
                ans = min(ans, cur);
                swap(s[x], s[y]);
            }
            T *= d;
        }
    }

    cout << ans << endl;

    return 0;
}

P3936 Coloring

代码

#include<iostream>
#include<ctime>
#include<random>
#include<cstring>
#define cpy(a, b) memcpy(a, b, sizeof(a));
#define ld long double
using namespace std;
const int N = 25;
const int C = 100;
const int INF = 0x3f3f3f3f;
const ld V = 1.8446e19l;

int n, m, c;
int p[C];
int a[N][N], b[N][N], aa[N][N];

int cur, ncur, ans;

mt19937_64 rng(clock());

inline int dist_int() { return rng() % (n * m); }
inline ld dist_ld() { return (ld)rng() / V; }

inline int gx(int p) { return p / m; }
inline int gy(int p) { return p % m; }

ld T, lim = 1e-15l, d = 0.99999l;

inline int calc(int x, int y) {
    int res = 0;
    if(x) res += (b[x][y] == b[x - 1][y]);
    if(y) res += (b[x][y] == b[x][y - 1]);
    if(x != n - 1) res += (b[x][y] == b[x + 1][y]);
    if(y != m - 1) res += (b[x][y] == b[x][y + 1]);
    return res;
}

void shuffle() {
    ncur = cur;
    int p1, p2, x1, y1, x2, y2;
    p1 = dist_int();
    do p2 = dist_int(); while(p2 == p1);
    x1 = gx(p1), y1 = gy(p1);
    x2 = gx(p2), y2 = gy(p2);
    ncur -= calc(x1, y1);
    ncur -= calc(x2, y2);
    swap(b[x1][y1], b[x2][y2]);
    ncur += calc(x1, y1);
    ncur += calc(x2, y2);
    bool flag = false;
    if(ncur > cur) flag = true;
    else if(dist_ld() <= exp(-(ld)(cur - ncur) / T)) flag = true;
    if(flag) {
        swap(a[x1][y1], a[x2][y2]);
        cur = ncur;
        if(cur > ans) {
            ans = cur;
            cpy(aa, a);
        }
    } else {
        swap(b[x1][y1], b[x2][y2]);
    }
}

int main() {

    cin >> n >> m >> c;
    for(int i = 1; i <= c; i++) cin >> p[i];
    for(int i = 0, k = 1; i < n; i++) {
        if(!(i & 1)) for(int j = 0; j < m; j++) {
            a[i][j] = k;
            if(!--p[k]) ++k;
        }
        else for(int j = m - 1; j >= 0; j--) {
            a[i][j] = k;
            if(!--p[k]) ++k;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cur += (i != n - 1 && a[i][j] == a[i + 1][j]) + (j != m - 1 && a[i][j] == a[i][j + 1]);
        }
    }

    cpy(b, a);

    int scnt = 0;
    int bg = clock();

    while(clock() - bg <= CLOCKS_PER_SEC * 9 / 10) {
        T = 1.0l;
        while(T > lim) {
            shuffle();
            T *= d;
        }
        ++scnt;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << aa[i][j] << ' ';
        }
        cout << endl;
    }

    cerr << "ans: " << ans << endl;
    cerr << "scnt: " << scnt << endl;

    return 0;
}

250520 模拟赛 T1

题意

有一张 \(n\) 个节点 \(m\) 条边的有向图。你可以进行若干次操作（至少一次），每次操作你选择一个节点 \(u\)，将 \(u\) 指向的所有节点的点权 --w[v]，将所有指向 \(u\) 的节点的点权 ++w[v]。最小化点权最大值。

\(n\le 50,\ m\le 1000\)
操作次数不应超过 \(10^5\)；

代码

#include<iostream>
#include<vector>
#include<random>
#include<ctime>
#include<unistd.h>
#define ld long double
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 55;
const int M = 1010;
const ull MASK = 0xffffffffffffffff;

int n, m;
vector<int> adj[N], rdj[N];

int cur, ncr;
int a[N], w[N];

mt19937_64 rng(clock());

ld dist_ld() { return (ld)rng() / MASK; }
int dist_int() { return (int)(rng() % n) + 1; }
bool dist_bool() { return rng() & 1; }

inline int calc() {
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, w[i]);
    return res;
}

ld temp, lim, stp;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        rdj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) a[i] = 1;
    for(int i = 1; i <= n; i++) {
        for(int v : adj[i]) --w[v];
        for(int v : rdj[i]) ++w[v];
    }

    cur = calc();

    lim = 1e-15;
    temp = 10;
    stp = 0.99999;

    while(temp >= lim) {
        int p = dist_int();
        int d = dist_bool() ? -1 : 1;
        if(a[p] == 0) d = 1;
        for(int v : adj[p]) w[v] -= d;
        for(int v : rdj[p]) w[v] += d;
        ncr = calc();
        bool flag = false;
        if(ncr <= cur) flag = true;
        else if(dist_ld() <= exp(-(ncr - cur) / temp)) flag = true;
        if(flag) {
            a[p] += d;
            cur = ncr;
        } else {
            for(int v : adj[p]) w[v] += d;
            for(int v : rdj[p]) w[v] -= d;
        }
        temp *= stp;
    }

    int sum = 0;
    for(int i = 1; i <= n; i++) sum += a[i];
    cout << sum << '\n';
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= a[i]; j++) cout << i << ' ';
    }
    cout << '\n';

    cerr << cur << endl;
    for(int i = 1; i <= n; i++) cerr << a[i] << ' ';
    cerr << '\n';

    return 0;
}