题目链接
这道题蒟蒻想了很久的状压\(dp\),即使我教练给我讲了思路我还是写挂了(还是太菜了Orz)
怒写一发模拟退火,在东方某神秘质数的加成下调了一下\(SA\)次数一发\(AC\)
可能我是欧皇?
感谢@黎曦の夜在讨论区的代码例子,让蒟蒻终于稍微明白了模拟退火的原理
分析:
这道题的做法非常多啊
蒟蒻把模拟退火单独分了一篇博客,望各位巨佬见谅蒟蒻的博客
既然知道了打通顺序,我们就可以知道打通所有点的最小代价,我们可以以打通的顺序作为解,然后套板子
#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;
}
原文:https://www.cnblogs.com/colazcy/p/11514735.html