题解 P2210 【Haywire】
ArachnidaKing · · 题解
题外话：有人说模拟退火是对一道好题的不敬，我说要是会写正解我自然会表示出对该题的敬意QAQ
首先声明！本题是一道模拟退火的练手好题！
模拟退火的概念较为简单，不懂的同学们可以先了解一下此篇洛谷日报。
本题虽为黑题，但实则比P1337 [JSOI2004]平衡点 / 吊打XXX简单一些。此篇题解不对模拟退火点的概念过多赘述，如有不懂可以看一下某位机房大佬（大机佬）的博客。这位大佬对模拟退火本身的讲解多，适合模拟退火入门的同学们。此篇题解对题目本身讲解多，以便同学们可以快速学会实际应用并可以类比用于其他题目。请同学们各取所需~
讲解尽在注释中——
#include<cstdio>
#define tin int//以下9行防手残
#define itn int
#define tni int
#define nit int
#define nti int
#define pritnf printf
#define scnaf scanf
#define retrun return
#define sizoef sizeof//以下9行是我懒
#define ld long double
#define inl inline
#define br break
#define con continue
#define mst(a,b) memset(a,b,sizeof(a))
#define fora(x,a,b) for(re tni x=a;x<=b;++x)
#define forb(x,a,b) for(re nit x=a;x>=b;--x)
#define re register
#define stt struct
#define infa 0x3f3f3f3f
#define infb 0x7fffffff
#define infd 0x7f
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxx(a,b) ((a)>(b)?(a):(b))//Tips：实测max()比大/小于计算慢了不止一点，所以自己写~
#define minn(a,b) ((a)<(b)?(a):(b))
#define pf(_) ((_)*(_))
typedef long long ll;
using namespace std;
const nit maxa=14;
const nit maxb=20;
const nit maxc=10;
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cmath>
//下面是四个参数，自己写模拟退火的时候多调一调，这便是模拟退火精髓所在。
const double zhongzhishijian=0.998;//终止时的时间，不一定要开这么大！（建议理解一下，考试时卡时限专用）
const double zhongzhiwendu=1e-16;//终止时的温度（循环边界，停止条件）
const double dertT=0.99;//每次温度变化量（每次循环，当前温度*这个数）
const double chushiwendu=1e7;//初始温度（不会模拟退火的话可以理解成对循环变量T初始化为一个较大数）
tni n,f[maxa][4],p[maxa]={0},pp[maxa]={0},rc=0,lsc,x,y;
/*
小蒟蒻最讨厌那些题解起一堆莫名其妙的字母、单词简称作变量名，经常让我看不懂！QAQ所以这里极力避免
n（Number of cows）：数据总数（牛的头数）。
f（friends）[i][j]：记录第i头牛的第j个好姬友。
p（最初地址/位置）[i]：存第i头牛的位置，用于作为每次循环开始时对pp[]赋值用的标准。
pp（当前地址/位置）：记录一次退火过程（循环过程）中牛们的实时位置。每退火一次，它就被p[]重新赋一次值，一点都不自由（雾）。
rc（Result Cost）：最终结果（全局最小化费）。
lsc（临时c（Lin Shi Cost））：“临时”用于与“全局当前最优值”rc区分。顾名思义，每次循环时被临时算出、使用、比较、抛弃（被覆盖）的值。
*/
inl tni qh();//（求和（Qiu He）：用于一次退火中每次循环求出当前解的优劣情况（具体看后面啦））。
inl void exc(tin x,tni y);//交换函数（EXChange）：用于将玄（随）学（机）求（得）出（到）的两头牛位置进行交换。
inl tni sj(tni a,tni b);//随机（Sui Ji）：用于科学地得出结果的函数。
tni mian()//主函数
{
srand(time(NULL));//最基本的随机种子
srand(rand()+19260817);//来自东方的神秘力量保佑我
srand(rand()+20021110);//我 保佑 我自己
srand(rand());//最后玄学一波
//
scanf("%d",&n);//输入牛的数目
fora(i,1,n)//宏定义的for循环编写方便，意为：循环变量i从1（register int i=1;）循环至n（i<=n;++i）
{
fora(j,1,3)
{
scanf("%d",&f[i][j]);//读入好姬友
}
p[i]=i;//为标准位置（初始位置）赋值（不会变）
pp[i]=i;//为一开始的即时位置赋初值（这里随意，用那个随机打乱函数都行）——是“赋初值”不是“赋值”，说明这个数组会改变，而上一个不会。
}
rc=qh();//用当前位置pp跑一边求和函数，得到初始解，用以以后被替换（本题求最小值，如果初值赋为零，srand（1......7）也救不了你），与rc=INF同作用。
//
while((clock()/(1.0*CLOCKS_PER_SEC))<=zhongzhishijian)//卡时专用，本人不太会描述，不懂的可以参见上面Ciyang的博客
{
lsc=rc;//每次循环用以作为临时值的lsc，
fora(i,1,n)
{
pp[i]=p[i];
}
//
for(re double T=chushiwendu;T>=zhongzhiwendu;T*=dertT)//降温过程
{
do//随机生成一组x，y两个数，表示交换pp数组中x，y位置的两头（天选之）牛
{
x=sj(1,n);//1-n的随机数
y=sj(1,n);//1-n的随机数，可能等于x
}
while(x==y);//理想状态下x！=y，但这样的概率还是有的不是吗？所以为了保险，只要相等就再随机生成一组（就看哪位欧皇在这个地方循环次数太多TLE了·^v·^）。
exc(x,y);//交换x，y位置的两头（天选之）牛。
lsc=qh();//求出交换后的花费，仅作临时比较之用。
if(lsc<=rc)//如果比全局最优解都优，还等什么，快赋给全局最优解啊！
{
rc=lsc;
}
//如果当前临时解比最优解差，我们也暂时不能扔！见下->
else if((1.0*exp(rc-lsc))/T>(1.0*rand()/RAND_MAX))//以一定的概率接受较差的新解，具体讲解见上面贴的Ciyang大佬的博客
{
exc(x,y);//换回去（不换回去（即接受命运的审判（较差的新解））的概率会越来越低，可以自行理解，exp函数用法见Ciyang大佬的博客）
}
}
}
//
printf("%d\n",rc/2);//为什么除以二？其实我们计算过程中一直得到的都是答案的2倍——每条a-b的路，计算a时算了一次，计算b时又算了一次（它好委屈）！
return 0；//完美收官
}
inl void exc(tin x,tni y)//互换基本操作
{
tni z=pp[x];
pp[x]=pp[y];
pp[y]=z;
//
return;
}
inl tni sj(tni a,tni b)//同为基本操作
{
return rand()%(b-a+1)+a;
}
inl tni qh()//sun是（每条路被算两次的）花费和！
{
tni sum=0;
fora(i,1,n)
{
fora(j,1,3)
{
sum+=abss(pp[i]-pp[f[i][j]]);
}
}
//
return sum;//如果你愿意，大可以return sum/2;然后输出的时候不/2~
}//本代码已进行防抄袭处理，欢迎复制粘贴并顺利CE！·^v·^ 替Ciyang大佬做了这么多广告……QAQ
挂一波友链：Ciyang大佬
顺便一提，用本题解参数跑出来会刚好每个点均为1000ms！实际上跑个200-300次就够了。