洛谷 P3959 宝藏
Description:
题目描述还是看链接吧，洛谷 markdown 复制过来有问题，不好意思，辛苦你们了。
题解：
这题看 dalao 们的题解都是什么随机算法，模拟退火。。。吓得我慌忙跑路。
蒟蒻的我只好用 状压dp 来水过。但这里还加了点深度优先搜索的味道
枚举每个起点， dis[i] 表示第 i 个点到起点的经过的宝藏的个数，f[i] 表示状态，表示当前找到宝藏的状态为 i 时，花费的代价的最小值。
然后我们开始深搜，用位运算更新状态，用最短路的思想更新距离，枚举每一个相邻的节点，搜完回溯就可以了。如此轻松快乐地水过此题。
表示依旧对 模拟退火 心有余悸！！！
贴代码：
1 #include<bits/stdc++.h> 2 #define inf 2147483647 3 using namespace std; 4 int n,m,g[20][20],f[10000],dis[20],ans=inf; 5 inline void search(int x) 6 { 7 for (int i=1; i<=n; i++) 8 if (1<<(i-1)&x) 9 { 10 for (int j=1; j<=n; j++) 11 if (((1<<(j-1))&x)==0 && g[i][j]!=inf) 12 { 13 if (f[x|(1<<j-1)]>f[x]+dis[i]*g[i][j]) 14 { 15 int tmp=dis[j]; 16 dis[j]=dis[i]+1; 17 f[x|(1<<(j-1))]=f[x]+dis[i]*g[i][j]; 18 search(x|(1<<(j-1))); 19 dis[j]=tmp; 20 } 21 } 22 } 23 } 24 int main() 25 { 26 scanf("%d%d",&n,&m); 27 for (int i=1; i<=n; i++) 28 for (int j=1; j<=n; j++) 29 g[i][j]=inf; 30 int u,v,z; 31 for (int i=1; i<=m; i++) 32 { 33 scanf("%d%d%d",&u,&v,&z); 34 g[u][v]=min(g[u][v],z); 35 g[v][u]=min(g[v][u],z); 36 } 37 for (int k=1; k<=n; k++) 38 { 39 for (int i=1; i<=n; i++) dis[i]=inf; 40 for (int i=1; i<=(1<<n)-1; i++) f[i]=inf; 41 dis[k]=1; f[1<<(k-1)]=0; 42 search(1<<(k-1)); ans=min(ans,f[(1<<n)-1]); 43 } 44 printf("%d",ans); 45 return 0; 46 }
加油加油加油！！！fighting fighting fighting!!!