Fork me on GitHub

【题解】luogu P2210 Haywire

发表于 | 分类于 |

明天就NOIP了我还在这里学玄学算法真的是要死啊QAQ

算了还是贴上一篇题解吧qwq，毕竟是人生中第一篇黑题题解qwq，

首先不会模拟退火的或者不会原理的请出门右转模拟退火原理+使用

看一下题目，可以发现这个题就是让我们在所有的组合中找出一个最优解来，符合我们模拟退火的使用条件，所以我们可以开始考虑如何确定每一个值了

剩下的注意的地方和一些做法就放在代码里了qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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时候又计算了所以必须除掉 
}

祝大家食用愉快qwq

召唤蕾姆