题意就是找一颗生成树,使代价最小。
考虑状压DP,在任意时刻,我们只关心集合里已经有那些点,且最大树高为多少
设要求的当前状态为$S$,那么这个状态要从$S$的子集中来,枚举子集$S_0$,判断出边所包含的点集$G_0$是否包含$S$,因为这样才能拓展到$S$,在这个条件成立的前提,判断新增的点有哪些,记为$ss$集合,之后$ss$集合的点取一条最短的边,与$s_0$的最深点连接起来,统计代价,至于为什么只是与最深的点连接,待会会解释。

对于一个集合$ss=S ~\operatorname{xor}~ S_0$和$S_0$,如果他们之间的边不是被$S_0$中最大深度的点连接成的,那么一定存在另一个$S_1$($S_1$也是$S$的子集),包含另一种连边的情况,使得$S_1$包含除被最大深度点连接的点以外的所有点,也就是$ss$部分点转移到了$S_1$中,仅有只与最大深度点连边的点集,才不能转移到$S_1$,那么通过$S_1$转移的答案就是最小值,一定是正确的。所以不会漏解。

$O(n^2*4^n)$的,可以改变枚举子集的顺序从而变成$O(n^2*3^n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=15,M=1<<12;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar(x%10+48);
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int g[M],f[M][N],d[N][N];
int main()
{
    int n,m;qr(n),qr(m);
    memset(d,0x3f,sizeof(d));
    for(int i=1;i<=m;i++)
    {
        int x,y,w;qr(x),qr(y),qr(w);--x,--y;
        d[x][y]=d[y][x]=min(d[x][y],w);
    }
    memset(f,0x3f,sizeof(f));
    int all=(1<<n)-1;
    for(int i=0;i<n;i++)d[i][i]=0;
    for(int i=1;i<=all;++i)
        for(int j=0;j<n;++j)if(((1<<j)|i)==i)
        {
            for(int k=0;k<n;++k)if(d[j][k]!=0x3f3f3f3f)
                g[i]|=1<<k;//边集合 
        }
    for(int i=0;i<n;i++)f[1<<i][0]=0;//枚举初始点
    for(int s=2;s<=all;s++)//母集,之后枚举子集 
        for(int s0=(s-1)&s;s0;s0=(s0-1)&s)if((g[s0]|s)==g[s0])
        {
            int sum=0;
            int ss=s^s0;//母集^子集
            for(int x=0;x<n;x++)if((1<<x)&ss)
            {
                int tmp=0x3f3f3f3f;
                for(int y=0;y<n;y++)if((1<<y)&s0)
                    tmp=min(tmp,d[x][y]);
                sum+=tmp;
            }
            for(int j=1;j<n;j++)if(f[s0][j-1]!=0x3f3f3f3f)
                f[s][j]=min(f[s][j],f[s0][j-1]+sum*j);
        }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;i++)ans=min(ans,f[all][i]);
    qw(ans);puts("");
    return 0;
}