【正经题解】宝藏

我们如果有一棵生成树，现在要往里面加入一个点
那么贪心的加边即可（枚举该点到生成树每一个点的连边）
当然上述做法显然有纰漏，如果这个点的最优路径端点不在生成树中，就不对了
但是如果给定一个加点序列，我们会发现上述贪心得出的是该排列下的最优解。
所以枚举全排列，之后贪心即可
那么仔细的看一下，其实贪心不仅是该选择排列下的最优解
还是深度序列下的最优解
我们枚举的全排列很多，但是对应的深度序列却很少
那么可不可以从深度开始思考呢？
我们设 $dp$ [ $i$ ][ $j$ ]表示一个有集合 $i$ ，最大深度为 $j$ 的生成树的代价之和
值为 $0x3f3f3f3f$ 为不存在
（似乎还有一个保存最后一层的数组，但这其实是不必要的）
那么转移的时候，如果 $i$ ， $j$ 存在
那么它的下一层可以是 $i$ 的补集的子集
也就是说要枚举 $i$ 的补集的子集，然后按刚才的贪心法则走
就能计算出下一个状态的值。
只是有一个问题，这样计算出的值显然偏大，并且永不偏小
因为我们把所有点的深度都按最大深度算了，
但是，我们可以证明，存在一些状态它们的值是准的
而问题的正解就在其中。你取 $min$ ，就可以滤掉错解
（好好想想，你要是每一层都恰好蒙对了，贪心出的路径就是上下两层之间的）
这样那个保存最后一层的数组就没有必要设了
另外有一个技巧，
设全集为 $s$ ，原集为 $j$
则 $int$ $k=s$ ^ $j$ ;
$for$ ( $int$ $i=k$ ; $i$ ; $i=$ ( $i-1$ )& $k$ )
可以便利 $j$ 补集的子集，同理如果把 $k$ 换成 $j$ 可以便利子集

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int dp[5000][20];
int n;int m;
int map[20][20];
int res=0x3f3f3f3f;int up;
int main()
{
    //代码丑请轻拍
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            map[i][j]=0x3f3f3f3f;
            map[j][i]=0x3f3f3f3f;
        }
    }
    for(int i=0;i<m;i++)
    {
        int u;int v;int val;
        scanf("%d%d%d",&u,&v,&val);
        u-=1;v-=1;
        if(map[u][v]>val)
        {
            map[u][v]=val;
            map[v][u]=val;
        }
    }
    up=pow(2,n);//计算状压的上界
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<up;j++)
        {
            dp[j][i]=0x3f3f3f3f;
        }
    }
    for(int i=0;i<n;i++)//边界条件
    {
        dp[1<<i][1]=0;
    }
    for(int i=1;i<=n;i++)//枚举状态
    {
        for(int j=0;j<up;j++)
        {
            if(dp[j][i]!=0x3f3f3f3f)//如果存在
            {
                //printf("dp[%d][%d]=%d\n",j,i,dp[j][i]);
                int k=(up-1)^j;
                for(int p=k;p;p=(p-1)&k)//枚举补集的子集
                {
                    int rep=0;
                    for(int st=0;st<n;st++)//贪心
                    {
                        if((p&(1<<st))!=0)//枚举属于最底层的起点
                        {
                            int minval=0x3f3f3f3f;
                            for(int ed=0;ed<n;ed++)//枚举属于已知树的终点
                            {
                                if((j&(1<<ed))!=0)
                                {
                                    if(minval>map[st][ed])//贪心
                                    {
                                        minval=map[st][ed];
                                    }
                                }
                            }
                            if(minval==0x3f3f3f3f)//不可能的树
                            {
                                goto ed;
                            }
                            rep+=minval;
                        }
                    }
                    rep*=i;//所有深度按最大深度计
                    dp[j|p][i+1]=min(dp[j|p][i+1],dp[j][i]+rep);//更新
                    //printf("->dp[%d][%d]=%d\n",j|p,i+1,dp[j|p][i+1]);
                    ed:;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)//更新解
    {
        res=min(res,dp[up-1][i]);
    }
    printf("%d",res);
    return 0;//拜拜程序~
}