题解 P3475 【[POI2008]POD-Subdivision of Kingdom】
Juan_feng
2019-03-25 11:47:00
## 小蒟蒻来水一篇退火题解
一看点这么少， 直接就上退火了qaq 稍微调了调参就过了qwqwq
做法就是先直接把点分成两份， 统计一下答案。 然后每次随机两个点交换， 在比较一下新答案和旧答案拿个更优， 以此来决定是直接接受还是概率性接受。 就没啥了？
另外有一点： 更新答案的时候， 我是直接扫了一遍所有的边，这样很明显效率不够高， 但是足以通过本题（最优解第一页） 那就留给大家作为思考内容吧qaq
那么代码如下：
```
#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]);
}
```