感觉这个题被玩坏了……
翻看了一下题解区，发现了(N)种神仙做法：
- 随机化搜索(伪模拟退火)
- 搜索+剪枝
- 模拟退火
- 不对但是能A的状压(DP)
- 正确的状压(DP)
其中(DP)又分用(DFS)的(DP)，不用(DFS)的(DP)，而且各种(DP)的时间复杂度也各不相同……
我还有什么话可说呢？
学习科学，使用玄学
——zhx
既然标签上都写了搜索和随机化了，那我们肯定要用第一种神仙做法(其实是因为我看不懂状压DP)
这里的随机化用到了一点模拟退火的思想，以一定的概率去接受新的连边方式，这个概率是随着(n)的上升而增大的
为了寻找最优解，我们可以让它多跑几遍，取最小值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 1000000
using namespace std;
int g[15][15],deth[15];
struct zzz{
int f,t;
}pass[1010]; int top;
bool operator < (struct zzz a,struct zzz b){
return deth[a.f]*g[a.f][a.t] > deth[b.f]*g[b.f][b.t];
}
bool vis[15];
int n,m;
int bfs(int s){
priority_queue <zzz> q;
int cost=0;
//将一开始的边入堆
for(int i=1;i<=n;i++)
if(g[s][i]<inf)
q.push(zzz{s,i});
//因为要多加(n-1)条边,所以循环到n-1
for(int i=1;i<n;i++){
zzz e=q.top(); q.pop();
while(!q.empty()&&(vis[e.t]||(rand()%n<1))){ //随机找边
if(!vis[e.t]) pass[++top]=e; //跳过的边仍然可能用到,先将它们存起来
e=q.top(); q.pop(); //随机一条新边
}
vis[e.t]=1; deth[e.t]=deth[e.f]+1;
for(int i=1;i<=top;i++) //将之前跳过的边在怼进堆里
q.push(pass[i]);
top=0;
for(int i=1;i<=n;i++)
if(g[e.t][i]<inf&&!vis[i]) //扩展新的边
q.push(zzz{e.t,i});
cost+=g[e.f][e.t]*deth[e.f];
}
return cost;
}
int read(){
int k=0; char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
k=k*10+c-48, c=getchar();
return k;
}
int main(){
srand(19****17); //打码保平安
memset(g,127/3,sizeof(g));
n=read(),m=read();
for(int i=1;i<=m;i++){ //因为点少边多,使用邻接矩阵存图更为方便
int x=read(),y=read();
g[x][y]=g[y][x]=min(g[x][y],read());
}
int ans=0x7fffffff;
for(int i=1;i<=500;i++) //为寻找最优解,多跑几遍
for(int i=1;i<=n;i++){ //枚举根节点
//初始化
memset(deth,127/3,sizeof(deth));
memset(vis,0,sizeof(vis));
deth[i]=vis[i]=1; top=0;
ans=min(ans,bfs(i))
}
cout<<ans;
return 0;
}
- 参考资料
题解 P3959【宝藏】——EternalAlexander