题解 P2210 【Haywire】
明天就NOIP了我还在这里学玄学算法真的是要死啊QAQ
算了还是贴上一篇题解吧qwq，毕竟是人生中第一篇黑题题解qwq，
首先不会模拟退火的或者不会原理的请出门右转模拟退火原理+使用
看一下题目，可以发现这个题就是让我们在所有的组合中找出一个最优解来，符合我们模拟退火的使用条件，所以我们可以开始考虑如何确定每一个值了
剩下的注意的地方和一些做法就放在代码里了qwq
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define re register
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int n;
int a[15][4];
int p[100],p1[101],linshi,x,y,dc;
const double starttem=1e9;
const double endtime=0.999;
const double changet=0.99;
const double endtem=1e-14;//mnth四位大大
int abss(int x)
{
return x>0?x:x*-1;
}
int sum() //求和
{
int ans=0;
for(re int i=1; i<=n; i++)
for(re int j=1; j<=3; j++)
ans+=abss(p1[i]-p1[a[i][j]]);
return ans;
}
inline void change(int x,int y) //交换两个值
{
int t=p1[x];
p1[x]=p1[y];
p1[y]=t;
}
int srandom(int a,int b) //非酋的最后一搏
{
return rand()%(b-a+1)+a;
}
int main()
{
srand(time(NULL));
srand(rand()+23333333);
srand(rand()+19260817);//东方之力祝我成功
srand(rand());//玄学四连
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
p[i]=i; //永远不变的初始位置
p1[i]=i;//变幻莫测的位置
}
dc=sum();//先求初始解
while((clock()/(1.0*CLOCKS_PER_SEC))<=endtime)
{
for(re int i=1; i<=n; i++) p1[i]=p[i]; //先初始化好初值
for(re double t=starttem; t>=endtem; t*=changet)
{
linshi=dc;
do
{
x=srandom(1,n);
y=srandom(1,n);
}while(x==y); //玩命找死
change(x,y);
linshi=sum();
if(linshi<=dc) dc=linshi; //看看是否比原先的更优
else if((exp(dc-linshi)*1.0/t>(rand()*1.0/RAND_MAX))) change(x,y); //用一定的概率接受该解（毕竟有比你优的，但是你肯定要把不优的换回去啊qwq
}
}
printf("%d",dc/2);//因为计算了两次，所以要除2，例如计算a-b你算a的时候计算了一次但你又在b时候又计算了所以必须除掉
}