状压DP求解最小生成树

最小生成树，一般我们会想到Kruskal或Prim，但是如果要求任意子图（仅限于包含部分结点和连接这些结点的所有完整的边）的最小生成树并且查询量很大呢？假设此处结点数量小于 \(20\)。

首先可以想到状态压缩，预处理出所有子图的最小生成树，但是这样如果 \(n\) 逼近 \(20\) 就不行了。状态共 \(2^n\) 种，建图需要 \(O(n)\)，求解需要 \(O(m \log m)\)，假设是完全图，那么时间复杂度可达到 \(O(2^n(n+m\log m))\)，即使不拆括号也很吓人了。如果稍微优化，预先排序，可以优化为 \(O(2^n m\log m)\)，但还是不够好，况且常数会极大，实际意义上，这种方法只能成为状态压缩，而不是状态压缩DP。

考虑动态转移方程。一个图的所有子图是预先处理好的，那么可以考虑生成树的性质。设结点数为 \(n\)，边为 \(n-1\)，那么可以从图中拆除一个点，再用图中剩下的点之一与那个被拆除的点连接，这样可以拼凑出原图，也能保证边数量为 \(n-1\)。若只有一个结点，很明显得出最小生成树的边权为 \(0\)。

for(int s=0;s<(1<<n);s++){
	if(__builtin_popcount(s)==1){
		dp[s]=0;
		continue;
	}
	for(int i=0;i<n;i++){
		if(s&(1<<i)){
			for(int j=0;j<n;j++){
				if((s&(1<<j))&&i!=j){
					dp[s]=min(dp[s],dp[s&(~(1<<i))]+f[i][j]);
				}
			}
		}
	}
}

这个思路的时间复杂度为 \(O(2^nn^2)\)，可以不那么费力地通过 \(n=20\) 的数据。而且再循环中已经优化了很多没必要的循环，这与上文的做法恰恰相反，而且状压DP常数低，再加上一些卡常，性能还是很卓越的。

状压DP写最小生成树是不是很奇怪？是我出题的时候的奇怪想法，貌似也没什么用