题解：P2210 Haywire

will1111 · 2024-09-08 09:59:42 · 题解

题解：P2210 Haywire

一道模拟退火的好题。

思路

模拟退火，每次任选两只奶牛交换位置，由于 4\le N\le 12，所以求出正确答案的概率足够高。

至于计算一个解需要耗费干草堆的数量，枚举 N 次，每次加上这头奶牛与其三个朋友的距离的和。

由于它和它的朋友各计算了一次，所以答案要除以 2。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<ctime>
#include<cmath>

using namespace std;

// 一些常量
const double init_tempeture=8000,cooling_speed=0.93,ending_tempeture=1e-4;

// 计算排列的值
int compute(vector<vector<int>>&frd,vector<int>&pos)
{
    int res=0;
    for(int i=1;i<frd.size();i++)
    {
        for(int j=0;j<3;j++)
        {
            res+=abs(pos[frd[i][j]]-pos[i]);
        }
    }
    return res/2;
}

int main()
{
    srand(time(0)); // 初始化随机
    int n;
    scanf("%d",&n);
    vector<vector<int>>frd(n+1,vector<int>(3)); // 记录朋友
    vector<int>pos(n+1); // 奶牛的位置
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&frd[i][0],&frd[i][1],&frd[i][2]);
    }
    int ans=1e9; // 全局最优解
    while(clock()<0.96*CLOCKS_PER_SEC)
    {
        for(int i=1;i<=n;i++) // 初始化位置
        {
            pos[i]=i;
        }
        double temp=init_tempeture;
        int now=1e9; // 局部最优解
        while(temp>ending_tempeture) // 开始退火
        {
            int x=rand()%n+1,y=rand()%n+1; // 随机交换
            while(x==y)
            {
                x=(rand()%n+n)%n+1;
                y=(rand()%n+n)%n+1;
            }
            swap(pos[x],pos[y]);
            int lcans=compute(frd,pos); // 计算答案
            if(lcans<=now) // 当前答案优于局部最优解，立即接受
            {
                now=lcans; // 修改局部最优解
            }
            else
            {
                if(exp(1.0*(now-lcans))/temp<1.0*rand()/RAND_MAX) // 概率接受
                {
                    swap(pos[x],pos[y]);
                }
            }
            temp*=cooling_speed;
        }
        ans=min(ans,now);
    }
    printf("%d\n",ans);
    return 0;
}