noip2017 宝藏（状压dp

分析

在变化的量是啥？已经打的点的集合，还有当前生成树的深度。
于是我们用 $f\left[s\right]\left[i\right]$f[s][i] 表示已打的集合为 $s$s ， 生成树深度为 $i$i 的最小代价。
转移的话，答案肯定是由 $S$S 的子集转移而来，我们就枚举子集，剩下的点作为第 $i$i 层，以此得到转移方程：
$f\left[S\right]\left[i\right]=min\left(f\right[S0\left]\right[i-1]+i\ast v[S0\left]\right[S$f[S][i]=min(f[S0][i−1]+i∗v[S0][S^ $S0\left]\right)$S0]) ( $S0$S0 是 $S$S 的子集， $v\left[S1\right]\left[S2\right]$v[S1][S2] 表示 将 $S2$S2 的点加入生成树 $S1$S1 的最小距离）
复杂度是 $O\left(n{3}^n\right)$O(n3n)

证明

让我们思考一下为什么这样转移是对的吧。
首先，肯定要有点作为第 $i$i 层，我们就相当于枚举这些点，于是 $f\left[S0\right][i-1]$f[S0][i−1] 就好理解了。
然后，贪心的想，对于两个集合要连通，我们选择的边肯定都是小的边。
需要理解的是，为什么代价是 $i\ast v\left[S0\right][S$i∗v[S0][S^ $S0]$S0] 呢？有疑惑的点在于为什么乘 $i$i。下面我们证明最优解一定会被覆盖到。
这其实考验对子集的理解。假如我们在转移的时候用的边不应该在第 $i$i 层，这条边连接的是 $(a,b)$(a,b)，其中 $a\in S0,b\in S$a∈S0,b∈S^ $S0$S0，那么我们在枚举到 $S+$S+{ $b$b}的时候，这条边就不计入转移了，就不存在该问题了。也就是说，我们转移的时候得到的临时答案，都是大于等于最终答案的，不存在比答案小的情况，也不会漏解。
不知道讲的清不清楚，有问题可以与我交流哈！！

upd

有一些状态是错误的，有一些状态是正确的，但是正确的状态比错误的状态优，因此最终答案肯定正确的。

代码如下

//f[i][s] = max(f[i-1][s0] + i * v[s0][s^s0])
#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
int f[12][1 << 12], v[1 << 12][1 << 12], g[1 << 12][12], mp[12][12], ans = inf;
int main(){
	int i, j, k, n, m, a, b, c, s, s0, sum;
	memset(f, 1, sizeof(f));
	memset(v, 1, sizeof(v));
	memset(g, 1, sizeof(g));
	memset(mp, 1, sizeof(mp));
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; i++){
		scanf("%d%d%d", &a, &b, &c);
		a--, b--;
		if(mp[a][b] > c) mp[a][b] = mp[b][a] = c;
	}
	/*for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(mp[i][j]) v[1 << i][1 << j] = mp[i][j];*/
	for(i = 0; i < (1 << n); i++){
		for(j = 0; j < n; j++){
			if(1 << j & i) continue;
			for(k = 0; k < n; k++) if(1 << k & i) g[i][j] = min(g[i][j], mp[j][k]);
			//printf("===%d %d %d\n", i, j, g[i][j]);
		}
	}
	for(i = 0; i < (1 << n); i++){
		s = (1 << n) - 1 - i;
		for(j = s; j; j = (j - 1) & s){
			sum = 0;
			for(k = 0; k < n; k++) if(1 << k & j) sum += g[i][k];
			v[i][j] = min(v[i][j], sum);
			//printf("===============%d %d %d\n", i, j, v[i][j]);
		}
	}
	for(i = 0; i < n; i++) f[0][1 << i] = 0;
	for(i = 1; i < n; i++){
		for(s = 0; s < (1 << n); s++){
			for(s0 = s; s0; s0 = (s0 - 1) & s) f[i][s] = min(f[i][s], f[i - 1][s0] + i * v[s0][s ^ s0]);
			//printf("%d %d %d\n", i, s, f[i][s]);
		}
	}
	for(i = 0; i < n; i++) ans = min(ans, f[i][(1 << n) - 1]);
	printf("%d", ans);
	return 0;
}