Haywire

题目链接

Haywire

分析

模拟退火裸题，交了 (4) 次

(Code)

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

int n , a[15][5] , pos[15] , tmp[15] , ans = 2e9;

int get_cost()
{
	int res = 0;
	for(register int i = 1; i <= n; i++) 
		for(register int j = 0; j <= 2; j++)
			res += abs(pos[i] - pos[a[i][j]]);
	return res;
}

void Simulate_Anneal()
{
	double T = 5000 , delta = 0.998;
	while (T > 1e-14)
	{
		for(register int i = 1; i <= n; i++) tmp[i] = pos[i];
		random_shuffle(pos + 1 , pos + n + 1);
		int c = get_cost() , del = c - ans;
		if (del < 0) ans = c;
		else if (exp(-del / T) * RAND_MAX > rand());
		else for(register int i = 1; i <= n; i++) pos[i] = tmp[i];
		T *= delta;
	}
}

int main()
{
	scanf("%d" , &n);
	for(register int i = 1; i <= n; i++) 
		scanf("%d%d%d" , &a[i][0] , &a[i][1] , &a[i][2]) , pos[i] = i;
	ans = get_cost();
	for(register int i = 0; i <= 50; i++) Simulate_Anneal();
	printf("%d" , ans / 2);
}