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
| #include <cstdio>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 15;
bool frd[N][N];
int n, mn = 500, cur, pos[N];
int rd(int l, int r)
{
return rand() % (r - l) + l;
}
double rd(double l, double r)
{
return (double)rand() / RAND_MAX * (r - l) + l;
}
int cal()
{
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (frd[i][j])
res += abs(pos[i] - pos[j]);
mn = min(mn, res / 2);
return res / 2;
}
void SimulateAnneal()
{
for (int i = 1; i <= n; i++)
pos[i] = i;
random_shuffle(pos + 1, pos + n + 1);
for (double t = 1e4; t > 1e-2; t *= 0.996)
{
int x = rd(1, n), y = rd(1, n);
while (x == y)
x = rd(1, n), y = rd(1, n);
cur = cal();
swap(pos[x], pos[y]);
int delta = cal() - cur;
if (exp(-delta / t) <= rd(0.0, 1.0))
swap(pos[x], pos[y]);
}
}
int main()
{
srand(time(NULL));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1, a; j <= 3; j++)
{
scanf("%d", &a);
frd[i][a] = true;
}
while ((double)clock() / CLOCKS_PER_SEC < 0.9)
SimulateAnneal();
printf("%d\n", mn);
return 0;
}
|