题解 P2210 【Haywire】

· · 题解

蒟蒻刚学模拟退火，来写一篇题解。

题目大意：每个点与其它三个点需要连边，连边代价为它们位置之差的绝对值。求一个排列使得这个值最小。

看到n都很小，虽然一般会想到状压，但是这题似乎不是一眼状压，考虑其它算法。

我们是不是可以随机一个数列，每次计算一下它的答案，根据一定次数的重复，从而得出一个可能的最优解呢？

我们可以用模拟退火。

考虑一次随机，我们做出的更改是交换这两个位置的点。那么每一次，我们的答案显然都会有一个改变。

计算这个答案，暴力即可；然后计算与当前答案的增量，以此判断是不是接受这个答案。

以此迭代，多迭代几次即可。

#include<bits/stdc++.h>
using namespace std;
int n;
const double h=0.996;
int a[50][50];
int ans;
int pos[50];
int calc(){
    int res=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=3;++j)
                res+=abs(pos[i]-pos[a[i][j]]);
    return res>>1;
}
void solve(){
    double T=6000;
    while(T>1e-16){
        int x=rand()%n+1;
        int y=rand()%n+1;
        swap(pos[x],pos[y]);
        int Num=calc();
        if(Num<ans)ans=Num;
        else if(exp(ans-Num)/T<double(rand())/RAND_MAX)swap(pos[x],pos[y]);
        T*=h;
    }
}
void work(){
    for(int i=1;i<=60;++i)solve();
    printf("%d\n",ans);
}
int main(){
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i][1]);
        scanf("%d",&a[i][2]);
        scanf("%d",&a[i][3]);
        pos[i]=i;
    }
    ans=2147483647;work();
    return 0;
}

话说这真是黑题吗……