작을 때는 전수 탐색, 클 때는 Simulated Annealing 이고 핵심은 최대한 빠르게 짜서 iteration 수를 확보하는 것
초반에 60점 나오길래 SA가 아닌가 했는데 그냥 잘못짠거였음

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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <cstdint> #include <climits> constexpr int MAXN = 128; constexpr int MAXM = 1024; int N, M; int curm, cur[MAXN], rev[MAXN]; struct {int x, y;} E[MAXM]; void solvePerfect(); void solveSA(); int main() { using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); int tc; cin >> tc; for (int t = 1; t <= tc; ++t) { cin >> N >> M; for (int i = M; i --> 0; ) cin >> E[i].x >> E[i].y; curm = INT_MAX; if (N < 9) solvePerfect(); else solveSA(); for (int i = N; i --> 0; ) rev[cur[i]] = i; cout << "Case #" << t << '\n' << curm << '\n'; for (int i = N; i --> 0; ) cout << rev[i] << ' '; cout << '\n'; } } // xorshiro256** // http://xoshiro.di.unimi.it/xoshiro256starstar.c static uint64_t rotl(uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } uint64_t rng() { static uint64_t s[4] = { 0x1234567890FABCDE, 999999999999999997, 333333333333333331, 0xDEADCAFEBA2EBA11,}; const uint64_t ret = rotl(s[1] * 5, 7) * 9; const uint64_t t = (s[1] << 17); s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 45); return ret; } static uint32_t rngd(uint32_t p) { return ((rng() >> 32) * p) >> 32; } static double rngf() { return double(rng() >> 11) / (UINT64_C(1) << 53); } // Helper functions static int32_t absi(int32_t x) { const int32_t y = (x >> 31); return ((x + y) ^ y); } static int calcRev() { int ret = 0; for (int i = M; i --> 0; ) ret += absi(rev[E[i].x] - rev[E[i].y]); return ret; } static void updateAnswer(int p) { curm = p; for (int i = N; i --> 0; ) cur[i] = rev[i]; } bool EE[10][10]; bool visited[12]; void dfs(int np, int depth) { rev[np] = depth; if (depth == 0) { const int ans = calcRev(); if (curm > ans) updateAnswer(ans); return; } --depth; visited[np] = true; for (int i = N; i --> 0; ) { if (visited[i]) continue; dfs(i, depth); } visited[np] = false; } void solvePerfect() { memset(EE, 0, sizeof(EE)); for (int i = M; i --> 0; ) EE[E[i].y][E[i].x] = EE[E[i].x][E[i].y] = true; for (int i = N; i --> 0; ) dfs(i, N - 1); } void solveSA() { constexpr double kl = 0.99995; constexpr int ITER1 = 102000; // 3.10s (199.107) constexpr int ITER2 = 8; for (int i = N; i --> 0; ) rev[i] = i; for (int i = N; --i > 0; ) std::swap(rev[i], rev[rngd(i)]); int np = calcRev(); updateAnswer(np); for (int zz = ITER2; zz --> 0; ) { double k = 256.0; for (int z = ITER1; z --> 0; k *= kl) { int wx = rngd(N), wy = rngd(N - 1); if (wy >= wx) ++wy; std::swap(rev[wx], rev[wy]); int xp = calcRev(); if (xp < curm) updateAnswer((np = xp)); else if (xp < np || exp((np - xp) / k) > rngf()) np = xp; else std::swap(rev[wx], rev[wy]); } } }