标签：模拟退火，搜索剪枝，状压DP
题目
[题目传送门](https://www.luogu.org/problemnew/show/P3959）
题目描述
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 \(n\) 个深埋在地下的宝藏屋， 也给出了这 \(n\) 个宝藏屋之间可供开发的\(m\) 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
\[\mathrm{L} \times \mathrm{K}\]L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。
输入输出格式
输入格式
第一行两个用空格分离的正整数 \(n,m\)，代表宝藏屋的个数和道路数。
接下来 \(m\) 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 \(1-n\)），和这条道路的长度 \(v\)。
输出格式
一个正整数，表示最小的总代价。
输入输出样例
输入样例#1
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
输出样例#1
4
输入样例#2
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
输出样例#2
5
说明
【样例解释1】
小明选定让赞助商打通了\(1\) 号宝藏屋。小明开发了道路 \(1 \to 2\)，挖掘了 \(2\) 号宝 藏。开发了道路 \(1 \to 4\)，挖掘了 \(4\) 号宝藏。还开发了道路 \(4 \to 3\)，挖掘了\(3\)号宝 藏。工程总代价为：\(1 \times 1 + 1 \times 1 + 1 \times 2 = 4\)
【样例解释2】
小明选定让赞助商打通了\(1\) 号宝藏屋。小明开发了道路 \(1 \to 2\)，挖掘了 \(2\) 号宝 藏。开发了道路 \(1 \to 3\)，挖掘了 \(3\) 号宝藏。还开发了道路 \(1 \to 4\)，挖掘了\(4\)号宝 藏。工程总代价为：\(1 \times 1 + 3 \times 1 + 1 \times 1 = 5\)
【数据规模与约定】
对于\(20\%\)的数据： 保证输入是一棵树，\(1 \le n \le 8\)，\(v \le 5000\) 且所有的 \(v\)都相等。
对于 \(40\%\)的数据： \(1 \le n \le 8\)，\(0 \le m \le 1000\)，\(v \le 5000\) 且所有的\(v\)都相等。
对于\(70\%\)的数据： \(1 \le n \le 8\)，\(0 \le m \le 1000\)，\(v \le 5000\)
对于\(100\%\)的数据： \(1 \le n \le 12\)，\(0 \le m \le 1000\)，\(v \le 500000\)
题解
考场上写了45pts的prim假算法
事实上加个模拟退火就AC了
写个模拟退火，总比去硬肝状压DP要划算吧
可惜去年NOIP我还不会模拟退火GG
code
45pts prim
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
struct edge{int to,self,w;}e[maxn<<1];
int dis[maxn],vis[maxn],n,m,cnt=0;
ll ans=1844387848,sum=0;
void dfs()
{
ll s=1,sum=0;
while(s<=n-1){
ll mi=1844387848,num;
rep(i,1,cnt)
if(vis[e[i].self]&&((ll)((dis[e[i].self]+1)*e[i].w)<mi)&&!vis[e[i].to]){
mi=e[i].w*(dis[e[i].self]+1);
num=i;
}
vis[e[num].to]=1;
dis[e[num].to]=dis[e[num].self]+1;
sum+=mi;
s++;
}
ans=min(ans,sum);
}
int main()
{
//freopen("treasure.in","r",stdin);
//freopen("treasure.out","w",stdout);
n=read(),m=read();
rep(i,1,m){
int x=read(),y=read(),z=read();
e[++cnt]=(edge){y,x,z};
e[++cnt]=(edge){x,y,z};
}
rep(i,1,n){
mem(vis,0);mem(dis,0);
vis[i]=1;dis[i]=0;
dfs();
}
cout<<ans<<endl;
return 0;
}
模拟退火AC代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=16;
int n,m,Map[maxn][maxn],deep[maxn],vis[maxn],ans=inf;
struct edge{int u,v;}e,et,past[maxn];
inline bool operator < (edge a,edge b){return deep[a.u]*Map[a.u][a.v]>deep[b.u]*Map[b.u][b.v];}
inline int search(int x){
mem(deep,0);mem(vis,0);mem(past,0);int p=0,cost=0;e.u=0,e.v=0;et.u=0,et.v=0;
priority_queue<struct edge>heap;
deep[x]=1;vis[x]=1;
rep(i,1,n)if(Map[x][i]<inf)e.u=x,e.v=i,heap.push(e);
rep(i,1,n-1){
e=heap.top();heap.pop();
while(!heap.empty()&&((vis[e.v]||rand()%n<1))){
if(!vis[e.v])past[p++]=e;
e=heap.top();heap.pop();
}
vis[e.v]=1;deep[e.v]=deep[e.u]+1;
if(p-->0)while(p>=0){heap.push(past[p]);p--;}
p=0;
rep(i,1,n)
if(Map[e.v][i]<inf&&!vis[i]){
et.u=e.v;et.v=i;
heap.push(et);
}
cost+=Map[e.u][e.v]*deep[e.u];
}
return cost;
}
int main()
{
n=read(),m=read();
mem(Map,0x3f3f3f);
rep(i,1,m){
int x=read(),y=read(),z=read();
Map[x][y]=Map[y][x]=min(z,Map[x][y]);
}
srand(1125);
rep(j,1,600){
rep(i,1,n)ans=min(ans,search(i));
}
cout<<ans<<endl;
return 0;
}
