# 一无所|知的小|J f

### 题解 P3475 【[POI2008]POD-Subdivision of Kingdom】

posted on 2019-03-25 11:47:00 | under 题解 |

## 小蒟蒻来水一篇退火题解

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define maxn 101
#define maxm 2002
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, t, x, y, z, mid, ans;
int a[maxn], b[maxn][maxm], pl[maxn], ss[maxn], l[maxm], r[maxm];
double delta = 0.996;

int pd(int x) {
return pl[x] > mid;
}

void SA() {
double t = 1926.0;
while(t > 1e-14) {
int qwq = rand()%mid+1;
int qaq = rand()%mid+mid+1;

swap(pl[a[qwq]], pl[a[qaq]]);
swap(a[qwq], a[qaq]);

int nans = 0;

FOR(i, 1, m) {
if(pd(l[i]) ^ pd(r[i]))
++nans;
}
int de = nans - ans;
if(de < 0) {
ans = nans;
FOR(i, 1, mid)
ss[i] = a[i];
}
else if(exp(-de/t)*RAND_MAX <= rand()){
swap(pl[a[qwq]], pl[a[qaq]]);
swap(a[qwq], a[qaq]);
}
t *= delta;
}
}

int main() {
srand(71806291);
srand(rand());
srand(rand());
scanf("%d%d", &n, &m);
mid = n/2;
FOR(i, 1, n)
a[i] = i, pl[i] = i;
//pl代表编号为i的点的位置   a代表i位置的点的编号
FOR(i, 1, n/2)
ss[i] = i;
FOR(i, 1, m) {
scanf("%d%d", &l[i], &r[i]);
if(pd(l[i]) ^ pd(r[i]))
++ans;
}

int st = 25;
while(st--) {
SA();
}

FOR(i, 1, n/2)
printf("%d ", ss[i]);
}