题目描述
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nn 个深埋在地下的宝藏屋， 也给出了这 nn 个宝藏屋之间可供开发的mm 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
mathrm{L} imes mathrm{K}L×K
L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。
输入输出格式
输入格式：
第一行两个用空格分离的正整数 n,mn,m，代表宝藏屋的个数和道路数。
接下来 mm 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 1-n1−n），和这条道路的长度 vv。
输出格式：
一个正整数，表示最小的总代价。
输入输出样例
说明
【样例解释1】
小明选定让赞助商打通了11 号宝藏屋。小明开发了道路 1 o 21→2，挖掘了 22 号宝 藏。开发了道路 1 o 41→4，挖掘了 44号宝藏。还开发了道路 4 o 34→3，挖掘了33号宝 藏。工程总代价为：1 imes 1 + 1 imes 1 + 1 imes 2 = 41×1+1×1+1×2=4
【样例解释2】
小明选定让赞助商打通了11 号宝藏屋。小明开发了道路 1 o 21→2，挖掘了 22 号宝 藏。开发了道路 1 o 31→3，挖掘了 33号宝藏。还开发了道路 1 o 41→4，挖掘了44号宝 藏。工程总代价为：1 imes 1 + 3 imes 1 + 1 imes 1 = 51×1+3×1+1×1=5
【数据规模与约定】
对于20\%20%的数据： 保证输入是一棵树，1 le n le 81≤n≤8，v le 5000v≤5000 且所有的 vv都相等。
对于 40\%40%的数据： 1 le n le 81≤n≤8，0 le m le 10000≤m≤1000，v le 5000v≤5000 且所有的vv都相等。
对于70\%70%的数据： 1 le n le 81≤n≤8，0 le m le 10000≤m≤1000，v le 5000v≤5000
对于100\%100%的数据： 1 le n le 121≤n≤12，0 le m le 10000≤m≤1000，v le 500000v≤500000
解题思路：
运用模拟退火的思路，先随意处理出一棵生成树，然后对这棵生成树的边进行修改，因为不确定根在哪个，就把每个都枚举一下，随机修改的时候可以找出决策点并进行退火算法
1#include<bits/stdc++.h>
2#define N 15
3#define int long long
4using namespace std;
5double T,start_T,del_T,low_T;
6int INF;
7int B[N],fa[N],n,Map[N+N][N+N],x,y,z,ans,m;
8double rand_double(){
9 return rand()/(double)RAND_MAX;
10}
11void addedge(int x,int y,int z){
12 Map[x][y]=min(Map[x][y],z);
13 Map[y][x]=min(Map[y][x],z);
14}
15void init(){
16 srand(6662333);//种子的选取很重要
17 start_T=23333;
18 del_T=0.99;
19 low_T=1e-9;
20 INF=12345678987654321;
21 ans=INF;
22 for (int i=0;i<=20;i++)
23 for (int j=0;j<=20;j++)
24 Map[i][j]=Map[j][i]=INF;
25}
26int find(int x){
27 if (x==B[x])
28 return x; else
29 return B[x]=find(B[x]);
30}
31void merge(int x,int y){
32 int fx=find(x);
33 int fy=find(y);
34 if (fx==fy) return;
35 B[fx]=fy;
36}
37int dfs_sum(int v,int Fa,int dep){
38// printf("call::dfs_sum(%lld, %lld, %lld)
", v, Fa, dep);
39// system("pause>nul");
40 int res=dep*Map[Fa][v];
41 for (int i=1;i<=n;i++){
42 if (fa[i]!=v||Fa==i) continue;
43 res+=dfs_sum(i,v,dep+1);
44 }
45// printf("dfs_sum(%lld, %lld, %lld) = %lld
", v, Fa, dep, res);
46 return res;
47}
48bool judge(){
49 for (int i=1;i<=n;i++)
50 B[i]=i;
51
52 for (int i=1;i<=n;i++){
53 bool skip=false;
54 if (find(i)==find(fa[i])) skip=true;
55 if (i!=fa[i]&&skip)
56 return false;
57 merge(i,fa[i]);
58 }
59 return true;
60}
61int SA_main(int root){//退火主要部分
62 int res=dfs_sum(root,0,0);
63// if (root != 1ll) printf("res = %lld
", res), system("pause");
64 T=start_T;
65 while (T>low_T){
66 int change,go;
67 do {
68 change=rand()%n+1;
69 go=rand()%n+1;
70 } while (change==go||change==root);
71 int deposit=fa[change];
72 fa[change]=go;
73 if (!judge()){
74 fa[change]=deposit;
75 continue;
76 }
77 int nxt=dfs_sum(root,0,0);
78 double depos=exp((res-nxt)/T);
79 if (nxt<res||depos>rand_double())
80 res=nxt; else
81 fa[change]=deposit;
82 T*=del_T;
83 }
84 //cout << res << endl;
85 return res;
86}
87void read(){
88 scanf("%lld%lld",&n,&m);
89 for (int i=1;i<=m;i++){
90 scanf("%lld%lld%lld",&x,&y,&z);
91 addedge(x,y,z);
92 }
93}
94void solve(){
95 if (n==1){
96 ans=0;
97 return;
98 }
99 for (int i=1;i<=n;i++){
100 for (int j=1;j<=n;j++)
101 fa[j]=i;//不要忘了每次初始化
102 fa[i]=0;
103 for (int j=1;j<=16;j++)//多搞几次增加正确率
104 ans=min(ans,SA_main(i));
105 }
106}
107void write(){
108 cout << ans << endl;
109}
110main(){
111 init();
112 read();
113 solve();
114 write();
115 return 0;
116}