大致题意：给你一张图，让你在图上选择一棵树，使每一条边的边权乘以其深度的总和最小。
随机算法
这道题的正解应该是树形状压DP，但是，毕竟DP太难打了。让我们仔细想一想，就会发现其实用随机化(Prim)就能AC此题。
我们可以循环(1000)次（但如果你人品够好就不需要(1000)次，如(hl666)大佬，(500)次就AC了，(200)次都有90分），只需每次枚举(1sim n)中的每一个点作为根，然后用随机算法乱搞即可。
代码
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define LL long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define N 12
#define M 1000
using namespace std;
int n,m,ans=2e9,ee=0,lnk[N+5],vis[N+5],Dep[N+5],dis[N+5],f[N+5][N+5];
struct edge
{
int from,to,nxt,val;
bool operator < (const edge x) const//排序的依据，使其新的深度乘以边权的值尽量小
{
return val*(Dep[from]+1)>x.val*(Dep[x.from]+1);
}
}e[2*M+5];
priority_queue<edge> h;
queue<edge> q;
inline char tc()
{
static char ff[100000],*A=ff,*B=ff;
return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0;int f=1;char ch;
while(!isdigit(ch=tc())) f=ch^'-'?1:-1;
while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
x*=f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void add(int x,int y,int z)
{
e[++ee].from=x,e[ee].to=y,e[ee].nxt=lnk[x],e[ee].val=z,lnk[x]=ee,
e[++ee].from=y,e[ee].to=x,e[ee].nxt=lnk[y],e[ee].val=z,lnk[y]=ee;
}
inline int SA(int x)//虽然函数名起的是SA（模拟退火），但其实根本没用到模拟退火的思想，只是纯粹的随机算法，具体过程类似于一个堆优化Prim
{
register int i;
//以下是预处理
memset(Dep,0,sizeof(Dep)),memset(vis,0,sizeof(vis)),memset(dis,0,sizeof(dis));//清空数组
while(!h.empty()) h.pop();//清空堆
while(!q.empty()) q.pop();//清空队列
//以上是预处理
vis[x]=1;//将当前节点（根）标记为已访问
for(i=lnk[x];i;i=e[i].nxt) h.push(e[i]);//将与根相连的边加入堆
for(register int t=1;t<n;++t)
{
edge k;
while(!h.empty()&&(vis[h.top().to]||!(rand()%n)))//只要当前边已被访问过，或者在1/n的概率下，跳过这条边
{
if(!vis[h.top().to]) q.push(h.top());//如果这条边不是因为被访问过而跳过，就将其储存下来，等到选完边后再加入堆
h.pop();//弹出
}
if(h.empty()) break;
k=h.top();h.pop();//将堆顶进行操作
while(!q.empty()) h.push(q.front()),q.pop();//将跳过的边重新放入堆
vis[k.to]=1,dis[k.to]=k.val,Dep[k.to]=Dep[k.from]+1;//更新
for(i=lnk[k.to];i;i=e[i].nxt)
if(!vis[e[i].to]) h.push(e[i]);//若该边连向的另一个节点未被访问过，就将这条边加入堆
}
int res=0;
for(i=1;i<=n;++i)
if(!vis[i]) return 2e9;else res+=Dep[i]*dis[i];//统计答案，若有点未被访问过，就返回一个超大值
return res;
}
int main()
{
register int i;int x,y,z;
for(read(n),read(m),i=1;i<=m;++i)
{
read(x),read(y),read(z);
if(f[x][y])//一个小优化，两点之间重复的边只存边权最小的一条
{
if(e[f[x][y]].val>z) e[f[x][y]].val=e[f[x][y]-1].val=z;
}
else add(x,y,z),f[x][y]=f[y][x]=ee;
}
srand(time(0)),srand(rand());//初始化随机函数，srand()两次防止被卡
for(register int t=1;t<=1000;++t)
for(i=1;i<=n;++i)
if((x=SA(i))<ans) ans=x;//更新答案
return write(ans),0;
}