[NOIP2017 TG D2T2]宝藏（模拟退火）-白红宇

[NOIP2017 TG D2T2]宝藏（模拟退火）

阅读量：6279 次

发布时间：2019-06-22

本文共 1744 字，大约阅读时间需要 5 分钟。

题目大意：$NOIPD2T2$宝藏

题解：正常做法：。这次模拟退火，随机一个排列，$O(n^2)$贪心按排列的顺序加入生成树

卡点：没开$long\;long$，接受较劣解时判断打错，没判$n=1$的情况

C++ Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 14const int inf = 0x3f3f3f3f;const int Tim = 20;const double ST = 500, DelT = 0.9, eps = 1e-5;inline int min(int a, int b) {return a < b ? a : b;}inline double rand_d() {return static_cast
          
            (rand()) / RAND_MAX;}int n, m;int e[maxn][maxn];int dep[maxn];struct node { int s[maxn]; long long ans; inline long long calc() { ans = 0; dep[s[1]] = 1; for (register int i = 2; i <= n; i++) { long long MIN = inf; for (register int j = 1; j < i; j++) if (e[s[i]][s[j]] != inf) { long long tmp = static_cast
           
             (dep[s[j]]) * e[s[i]][s[j]]; if (tmp < MIN) MIN = tmp, dep[s[i]] = dep[s[j]] + 1; } ans += MIN; } return ans; }} ans, now, nxt;void SA() { double T = ST; long long del; now = ans; while (T > eps) { int x = rand() % n + 1, y = rand() % n + 1; while (x == y) x = rand() % n + 1, y = rand() % n + 1; nxt = now; std::swap(nxt.s[x], nxt.s[y]); del = nxt.calc(); if (del < now.ans || exp((now.ans - del) / T) > rand_d()) now = nxt; if (del < ans.ans) ans = nxt; T *= DelT; }}int main() { srand(20040826); scanf("%d%d", &n, &m); if (n == 1) { puts("0"); return 0; } for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) e[i][j] = e[j][i] = inf; } for (int i = 1, a, b, c; i <= m; i++) { scanf("%d%d%d", &a, &b, &c); e[b][a] = e[a][b] = min(e[a][b], c); } int __Tim = Tim; for (int i = 1; i <= n; i++) ans.s[i] = i; ans.calc(); while (__Tim --> 0) SA(); printf("%lld\n", ans.ans); return 0;}