算法

(状态压缩DP) $O(n^2 3^n)$

状态压缩DP，下文中 i 是一个 n 位二进制数，表示每个点是否存在。

状态定义：

• f[i][j] 表示：
  • 集合：所有包含 i 中所有点，且树的高度等于 j 的生成树。
  • 属性：最小花费。

状态计算：

枚举 i 的所有非全集子集 S 作为前 j - 1 层的点，剩余点作为第 j 层的点。

核心：

求出第 j 层的所有点到 S 的最短边，将这些边权和乘以 j，直接加到 f[S][j - 1] 上，即可求出 f[i][j]。

证明：

将这样求出的结果记为 f'[i][j]。

• f[i][j] 中花费最小的生成树一定可以被枚举到，因此 f[i][j] >= f'[i][j]。
• 如果第 j 层中用到的某条边 (a, b) 应该在比 j 小的层，假设 a 是 S 中的点，b 是第 j 层的点，则在枚举 S + {b} 时会得到更小的花费，即这种方式枚举到的所有花费均大于等于某个合法生成树的花费，因此 f[i][j] <= f'[i][j]。

所以有 f[i][j] = f'[i][j]。

时间复杂度

包含 $k$ 个元素的集合有 $C(n, k)$ 个，且每个集合有 $2^k$ 个子集，因此总共有 $C(n, k) * 2^k$ 个子集。$k$ 可以取 $0∼n$，则总共有 = $3^n$，这一步由二项式定理可得。

对于每个子集需要 $n^2$ 次计算来算出剩余点到子集中的最短边。

因此总时间复杂度是 O($n^2 * 3^n$)。

#include<bits/stdc++.h>
using namespace std;
const int N=12,M=1<<N,INF=0x3f3f3f3f;
int n,m;
int d[N][N],g[N][M]; //d[i][j]表示i到j的最短距离,g[i][j]表示i点到j集合中的距离 
int f[M][N]; //f[i][j] 表示点集i一共j层的最小值 
int main()
{
	cin>>n>>m;
	memset(d,0x3f,sizeof d);
	for(int i=0;i<n;i++) d[i][i]=0;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		d[a][b]=d[b][a]=min(d[a][b],c); //去重得到最小距离 
	}
	memset(g,0x3f,sizeof g);//初始化距离
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<1<<n;j++)
		{
			for(int k=0;k<n;k++)
			{
				if(j>>k&1) //说明j集合中包含k点 
				{
					g[i][j]=min(g[i][j],d[i][k]) ;//更新i到j集合的距离 
				}		
			}
		}	
	} 
	memset(f,0x3f,sizeof f); //初始化 
	for(int i=0;i<n;i++) //初始化每个点为根 
	{
		f[1<<i][0]=0;
	}
	for(int i=1;i<1<<n;i++) //枚举所有情况 
	{
		for(int j=i-1&i;j;j=j-1&i) //枚举所有子集 
		{
			int r=i^j;//剩余部分(在j-1层) 
			int cost=0;
			for(int k=0;k<n;k++)
			{
				if(j>>k&1)
				{
					cost+=g[k][r];	
					if(cost>=INF) break; 
				}	
			} 
			if(cost>=INF) continue;
			for(int k=1;k<n;k++) //枚举前面的最小值 
			{
				f[i][k]=min(f[i][k],f[r][k-1]+cost*k); //当前放到哪一层 
			}
		}
	}
	int res=INF;
	for(int i=0;i<n;i++) //枚举所有点在前i层 
	{
		res=min(res,f[(1<<n)-1][i]);
	}
	cout<<res;
	return 0;
}