[luogu2210] Haywire

题意

Here

思考

为了 (NOIP) 前练习玄学算法模拟退火，于是 (A) 了这道 黑题，这题正解好像是 (A^*?)

先随机一波排列，然后随机两头牛来交换位置进行退火，但总之这是个玄学看脸算法（雾）

代码

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x * f;
}
typedef double D;
const int N = 30;
int n, ANS, sum, f[N][4], ans[N], pos[N];
int calc(){
    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=3; j++){
            ans += abs( pos[i] - pos[f[i][j]] );
        }
    }
    return ans;
}
void SA(){
    D t = 10000;
    while(t > 1e-14){
        int x, y;
        do{
            x = rand() % n + 1, y = rand() % n + 1;
        }while(x == y);
        swap(pos[x], pos[y]);
        int nowans = calc();
        if(nowans < ANS){
            ANS = nowans;
        }
        else {
            if( exp( (ANS - nowans) / t ) > (double) rand() / RAND_MAX ){
                swap(pos[x], pos[y]);
            }
        }
        t *= 0.99;
    }
}
int main(){
    srand(time(0));
    n = read();
    for(int i=1; i<=n; i++) ans[i] = pos[i] = i;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=3; j++) f[i][j] = read();
    ANS = calc();
    int len = 200;
    while(len --) SA();
    cout << ANS / 2;
    return 0;
}

总结

注意调参
话说有一个问题：

我在洛谷提交的时候一直爆零，是因为我构造了一个 (random) 函数，是这样的：

int random(int x){
    return rand() * rand() % x + 1;
}

但是一直 (WA)，只要直接 (rand()) 就过了，不知道为啥，如果知道的同学可以告诉我一声 (QWQ) 感谢~