Luogu P3959 宝藏

本人第一道随机化算法题。
首先，我们可以想到考虑建生成树中扩展点的顺序。易知如果将$n$的全排列判定一遍，就一定能得到最优解。
但是显然对于$n \leq 12$，$n$的全排列不可做，所以就可以用到随机化。每次建生成树时，随机拿出一个$n$的排列作为扩展点的顺序。即以下代码：

random_shuffle(ord+1,ord+n+1);

然后，因为生成树的源点是不固定的，所以建树的时候要枚举一遍$n$作为生成树的源点。然后扩展时考虑边的可行性即可。

#include<bits/stdc++.h>
#define N 20
#define M 1010
#define INF 0x3f3f3f3f

using namespace std;

int n,m;
int dep[N],ord[N],dis[N][N];
long long ans=INF,sum;

void Init() {
    for(int i=1;i<=n;i++) {
        dep[i]=0;
    }
    sum=0;
    return;
}

void Read() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            dis[i][j]=INF;
        }
        dis[i][i]=0;
        ord[i]=i;
    }
    for(int i=1;i<=m;i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v]=min(w,dis[u][v]);
        dis[v][u]=min(w,dis[v][u]);
    }
    return;
}

void Kruskal() {
    Init();
    random_shuffle(ord+1,ord+n+1);
    dep[ord[1]]=1;
    for(int i=2;i<=n;i++) {
        int t=ord[i],tmpu=0,tmpw=INF;
        for(int j=1;j<=n;j++) {
            if(!dep[j]||dis[j][t]==INF) {
                continue;
            }
            else if(dis[j][t]*dep[j]<tmpw) {
                tmpw=dis[j][t]*dep[j];
                tmpu=j;
            }
        }
        if(tmpu) {
            dep[t]=dep[tmpu]+1;
            sum+=tmpw;
        }
        else {
            return;
        }
    }
    ans=min(sum,ans);
    return;
}

void Solve() {
    for(int i=1;i<=100000;i++) {
        Kruskal();
    }
    printf("%lld",ans);
}

int main()
{
    Read();
    Solve();
    return 0;
}