我们都爱膜您退火！

写了模板题(伪)洛谷P1337 平衡点，发现这跟骑行川藏毫无可比性......

骑行川藏简直就是退火地狱，这个模板题就容易的多了...随便搞几下就过了。

一些心得：

1.最好在函数值连续的时候使用模拟退火。

2.想要把精度控制的高，重要的不是eps，而是把△T调小。这样在T很小的时候会随机足够多的次数从而让精度更进一步。

3.正确性的核心在于每次随机调整出来的解的变化幅度与T相关。

例题：骑行川藏。

洛谷P1337，这东西很好退吧...

#include <bits/stdc++.h>

const int N = 1010;
const double eps = 1e-7, dT = 0.999;

struct Vec {
    double x, y;
    Vec(double X = 0, double Y = 0) {
        x = X, y = Y;
    }
    inline Vec operator + (const Vec &w) const {
        return Vec(x + w.x, y + w.y);
    }
    inline Vec operator - (const Vec &w) const {
        return Vec(x - w.x, y - w.y);
    }
    inline double operator & (const Vec &w) const {
        return x * w.x + y * w.y;
    }
    inline double operator * (const Vec &w) const {
        return x * w.y - y * w.x;
    }
    inline Vec operator * (const double &w) const {
        return Vec(x * w, y * w);
    }
    inline Vec operator / (const double &w) const {
        return Vec(x / w, y / w);
    }
};
typedef Vec Poi;

Poi a[N];
int n;
double W[N];

inline double len(Vec x) {
    return sqrt(x & x);
}

inline double cal(double x, double y) {
    //printf("cal : %lf %lf 
", x, y);
    Vec ans(0, 0), now(x, y);
    for(int i = 1; i <= n; i++) {
        if(fabs(y - a[i].y) < eps && fabs(x - a[i].x) < eps) continue;
        Vec temp = (a[i] - now) / len(a[i] - now) * W[i];
        ans = ans + temp;
    }
    /*printf("ansx = %lf ansy = %lf 
", ans.x, ans.y);
    puts("");*/
    return len(ans);
}

inline double Rand(double l, double r) {
    return (double)rand() / RAND_MAX * (r - l) + l;
}

inline void Fire() {
    double x1 = 1e7, x2 = -1e7, y1 = 1e7, y2 = -1e7;
    for(int i = 1; i <= n; i++) {
        x1 = std::min(x1, a[i].x);
        x2 = std::max(x2, a[i].x);
        y1 = std::min(y1, a[i].y);
        y2 = std::max(y2, a[i].y);
    }

    double px((x2 + x1) / 2), py((y2 + y1) / 2), fx(px), fy(py), T(std::max(y2 - y1, x2 - x1));
    double ans = cal(px, py), fin = ans;

    while(T > eps) {

        double x = px + T * Rand(-1, 1), y = py + T * Rand(-1, 1);
        x = std::max(x, x1);
        x = std::min(x, x2);
        y = std::max(y, y1);
        y = std::min(y, y2);
        double New = cal(x, y);
        //printf("New = %lf 
", New);

        if(New < fin) {
            fin = New;
            fx = x;
            fy = y;
        }
        if(New < ans || Rand(0, 1) < exp((ans - New) / T)) {
            ans = New;
            px = x;
            py = y;
        }
        /*printf("fin = %lf fx = %lf fy = %lf
", fin, fx, fy);
        printf("ans = %lf px = %lf py = %lf
", ans, px, py);
        printf("T = %lf New = %lf 
", T, New);
        puts("");*/
        T *= dT;
    }
    printf("%.3f %.3f
", fx, fy);
    return;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf%lf", &a[i].x, &a[i].y, &W[i]);
    }

    Fire();

    return 0;
}

LOJ#512 春游(提答)

题意：把n个小动物分成K组，使得每组的权值最大值最小。有m个约束形如两个小动物在一组会把权值 + a或者 × b，先加后乘。

解：用时约2h，得分69。

模拟退火。先随机分组，然后随机一个小动物改变到一个随机组里。权值的变化：枚举别的所有点，邻接矩阵存边权。权值的计算：每个组维护一个add和mul，暴力枚举所有组算权值。

#include <bits/stdc++.h>

const int N = 100010;

struct Node {
    int x, y, f, z;
    double w;
}node[N];

inline int rd(int l, int r) {
    return rand() % (r - l + 1) + l;
}
inline double Rand() {
    return (double)(rand()) / RAND_MAX;
}

int n, K, m, val[N], val2[N], testid;
int fr[N], Fin[N];
int G1[5010][5010], G2[5010][5010], add[N];
double G3[5010][5010], mul[N];
std::vector<int> v[N];

inline double calMax() {
    double ans(0);
    for(register int i(1); i <= K; ++i) {
        ans = std::max(ans, mul[i] * add[i]);
    }
    return ans;
}

inline void Fire() {
    
    for(int i = 1; i <= K; i++) {
        add[i] += val2[i];
        mul[i] = 1;
    }
    for(int i = 1; i <= n; i++) {
        fr[i] = rd(1, K);
        add[fr[i]] += val[i];
        for(int j = 1; j < i; j++) {
            if(fr[i] != fr[j] || !G1[i][j]) {
                continue;
            }
            if(G1[i][j] == 1) {
                add[fr[i]] += G2[i][j];
            }
            else {
                mul[fr[i]] *= G3[i][j];
            }
        }
    }
    
    double ans = calMax(), fin = ans;
    memcpy(Fin + 1, fr + 1, n * sizeof(int));
    
    double T = 10000, dT = 0.9999, edT = 1e-7;
    while(T > edT) {
        
        int x = rd(1, n), y = rd(1, K);
        while(y == fr[x]) {
            y = rd(1, K);
        }
        std::swap(fr[x], y);
        add[y] -= val[x];
        add[fr[x]] += val[x];
        for(int i = 1; i <= n; i++) {
            if(!G1[x][i] || (fr[i] != y && fr[i] != fr[x])) {
                continue;
            }
            if(fr[i] == fr[x]) {
                if(G1[x][i] == 1) {
                    add[fr[x]] += G2[x][i];
                }
                else {
                    mul[fr[x]] *= G3[x][i];
                }
            }
            else {
                if(G1[x][i] == 1) {
                    add[y] -= G2[x][i];
                }
                else {
                    mul[y] /= G3[x][i];
                }
            }
        }
        double nex = calMax();
        //printf("T = %lf nex = %lf 
", T, nex);
        if(fin > nex) {
            fin = nex;
            memcpy(Fin + 1, fr + 1, n * sizeof(int));
            printf("fin = %lf 
", fin);
        }
        if(nex < ans || Rand() < exp((ans - nex) / T)) {
            ans = nex;
        }
        else {
            std::swap(fr[x], y);
            add[y] -= val[x];
            add[fr[x]] += val[x];
            for(int i = 1; i <= n; i++) {
                if(!G1[x][i] || (fr[i] != y && fr[i] != fr[x])) {
                    continue;
                }
                if(fr[i] == fr[x]) {
                    if(G1[x][i] == 1) {
                        add[fr[x]] += G2[x][i];
                    }
                    else {
                        mul[fr[x]] *= G3[x][i];
                    }
                }
                else {
                    if(G1[x][i] == 1) {
                        add[y] -= G2[x][i];
                    }
                    else {
                        mul[y] /= G3[x][i];
                    }
                }
            }
        }
        T *= dT;
    }
    
    for(int i = 1; i <= n; i++) {
        v[Fin[i]].push_back(i);
    }
    
    char buf[100];
    sprintf(buf, "spring%d.out", testid);
    freopen(buf, "w", stdout); 
    
    for(int i = 1; i <= K; i++) {
        int len = v[i].size();
        printf("%d
", len);
        for(int j = 0; j < len; j++) {
            printf("%d ", v[i][j]);
        }
        puts("");
    }
    fclose(stdout);
    return;
}

int main(int argc, char **argv) {

    srand(time(0));

    if(argc != 2) return 0;
    testid = atoi(argv[1]);
    char buf[100];
    sprintf(buf, "spring%d.in", testid);
    freopen(buf, "r", stdin);

    scanf("%d%d%d", &n, &K, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &val[i]);
    }
    for(int i = 1; i <= K; i++) {
        scanf("%d", &val2[i]);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d", &node[i].f, &node[i].x, &node[i].y);
        int x = node[i].x, y = node[i].y;
        G1[x][y] = G1[y][x] = node[i].f;
        if(node[i].f == 1) {
            scanf("%d", &node[i].z);
            G2[x][y] = G2[y][x] = node[i].z;
        }
        else {
            scanf("%lf", &node[i].w);
            G3[x][y] = G3[y][x] = node[i].w;
        }
    }
    fclose(stdin);
    
    Fire();
    
    return 0;
}