题解：P2210 Haywire

· · 题解

前言

笔者是一个刚学模拟退火的蒟蒻，有写的不好的地方欢迎大家指出。

题目大意

有 N 头奶牛，每一头奶牛有三个朋友，奶牛们都住在一条线上，如果有两头奶牛是朋友，那么他们之间就需要一条线路，线路的长度为两头奶牛的距离，现在求最短的总线路距离。

思路

如果是直接枚举全排列的话，那么显然会超时，所以考虑用模拟退火。模拟退火是一个优化暴力的东西，但是因为引入了更多的随机的因数，所以找到正解的概率大大增加。

那么应该退火什么呢？由枚举全排列可知，我们可以每次随机出来两个数，这两个数表示两头奶牛，然后我们让这两头奶牛交换它们的位置，就可以得到新的排列。

所以我们可以用一个数组记录奶牛的位置，下标 i 表示是第 i 头奶牛，而里面的值表示第 i 头奶牛在哪个位置。那么我们每次随机出两个数 x 和 y，然后 swap(x,y) 即可。

PS：如果随机出两个数相同，可以直接跳过，节省时间。

具体见代码：

#include<bits/stdc++.h>
using namespace std;
const double T=2000.0,TD=0.999,TK=1e-15;//初始温度 T，每次下降温度的系数 TD，以及终止温度 TK。
long long n,a[15][4],b[15],answer=1e18;//answer 初始值应当是无穷大
long long calculate()//计算这个排列的答案
{
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=abs(b[i]-b[a[i][1]])+abs(b[i]-b[a[i][2]])+abs(b[i]-b[a[i][3]]);
    }
    return sum/2;//因为同时从 i 和 a[i] 计算了一次，所以要除以二
}
void sa()//模拟退火
{
    double t=T;//初始温度
    while(t>TK)
    {
        long long ex=rand()%n+1,ey=rand()%n+1;//随机出两个数
        if(ex==ey)continue;
        swap(b[ex],b[ey]);//产生新的排列
        long long eans=calculate();
        long long de=eans-answer;
        if(de<0)//答案更优秀
        {
            answer=eans;
        }
        else
        {
            if(exp(de/t)>rand())//这里是如果按一定概率接受答案没有接受，就把答案改回来
            {
                swap(b[ex],b[ey]);
            }
        }
        t*=TD;//降温
    }
    return;
}
int main()
{
    srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        b[i]=i;
        cin>>a[i][1]>>a[i][2]>>a[i][3];//输入 i 头奶牛的三个朋友
    }
    sa();//多跑几次模拟退火
    sa();
    sa();
    sa();
    sa();
/*
如果你不放心，可以用这个踩着时间限制过去：
while(clock()<90000)sa();
*/
    cout<<answer;
    return 0;
}

记录