一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

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

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

小蒟蒻来水一篇退火题解

一看点这么少, 直接就上退火了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]);
}