题目链接
这道题蒟蒻想了很久的状压\(dp\),即使我教练给我讲了思路我还是写挂了(还是太菜了Orz)

怒写一发模拟退火,在东方某神秘质数的加成下调了一下\(SA\)次数一发\(AC\)

可能我是欧皇?

感谢@黎曦の夜在讨论区的代码例子,让蒟蒻终于稍微明白了模拟退火的原理

Solution [NOIP2017]宝藏

题目大意:给定一个\(n\)个点\(m\)条边的无向图,给定了加入一条边的代价,求一个打通顺序,使得打通所有点的总代价最小

分析:

这道题的做法非常多啊

• Prim 各位巨佬证明了\(Prim\)算法是错误的,只能得\(45\)分，蒟蒻也就不在这里赘述了。
• 状压\(dp\) 前面蒟蒻写挂了才写的模拟退火,而且状压\(dp\)好像没有模拟退火快吧?
• 模拟退火 这是本篇题解所用的算法

蒟蒻把模拟退火单独分了一篇博客,望各位巨佬见谅蒟蒻的博客

既然知道了打通顺序,我们就可以知道打通所有点的最小代价,我们可以以打通的顺序作为解,然后套板子

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 16;
int g[maxn][maxn],n,m;
struct Node{
    int d[maxn],deep[maxn];
    Node(){
        for(int i = 1;i <= n;i++)
            d[i] = i,deep[i] = 0;
    }
    Node(const Node &rhs){
        memcpy(d,rhs.d,sizeof(d));
        memset(deep,0,sizeof(deep));
    }
    Node operator = (const Node &rhs){
        memcpy(d,rhs.d,sizeof(d));
        memset(deep,0,sizeof(deep));
        return *this;
    }
    inline int solve(){//按照打通顺序求代价
        int ret = 0;
        deep[d[1]] = 1;//第一个打通的节点深度为1
        for(int i = 2;i <= n;i++){
            int temp = 0x7fffffff;
            for(int j = 1;j < i;j++){//枚举由哪一个已经打通的节点打通道路
                if(g[d[i]][d[j]] != 0x3f3f3f3f && deep[d[j]] * g[d[i]][d[j]] < temp)
                    temp = deep[d[j]] * g[d[i]][d[j]],deep[d[i]] = deep[d[j]] + 1;
            }
            if(temp == 0x7fffffff)return 0x7fffffff;//当前方案不可行可以提前退出了
            ret += temp;
        }
        return ret;
    }
};
inline int SA{//SA
    const double max_temp = 10000.0;//初始温度
    const double delta_temp = 0.98;//降温系数
    double temp = max_temp;//当前温度
    Node path;//打通顺序
    while(temp > 0.1){
        Node tpath(path);
        swap(tpath.d[rand() % n + 1],tpath.d[rand() % n + 1]);//随机一个新解
        double delta = tpath.solve() - path.solve();//求解
        if(delta < 0)path = tpath;//如果新解更优,则接受
        else if(exp(-delta / temp) * RAND_MAX >= rand())path = tpath;//否则以一定概率接受
        temp *= delta_temp;
    }
    return path.solve();
}
int main(){
    srand(19260817);//东方神秘质数
    memset(g,0x3f,sizeof(g));
    scanf("%d %d",&n,&m);
    for(int u,v,d,i = 1;i <= m;i++){
        scanf("%d %d %d",&u,&v,&d);
        g[u][v] = min(g[u][v],d);
        g[v][u] = min(g[v][u],d); 
    }//存图
    int ans = 0x7fffffff;
    for(int i = 1;i <= 233;i++)//跑SA,取最优值
        ans = min(ans,SA());
    printf("%d\n",ans);
    return 0;
}

题解 P3959 【宝藏】

原文：https://www.cnblogs.com/colazcy/p/11514735.html