设$f_{d, s}$表示当前树的深度为$d$，与第一个打通的点连通的点集为$s$。
每次转移的时候不考虑实际的深度，深度都当做$d$，寻找连接两个点集最小边集，如果能连接更浅的点，那么会在之前转移，所以即使转移非法也不可能成为最优解。
找连接两个点集的最小边集合可以预处理。
我比较懒，不想预处理，时间复杂度$O(n^{2}3^{n})$。
Code
1 /** 2 * uoj 3 * Problem#333 4 * Accepted 5 * Time: 123ms 6 * Memory: 1412k 7 */ 8 #include <iostream> 9 #include <cstdlib> 10 #include <cstdio> 11 using namespace std; 12 typedef bool boolean; 13 14 const int N = 12, S = 1 << N; 15 const signed inf = (signed) (~0u >> 1); 16 17 template <typename T> 18 void pfill(T* pst, const T* ped, T val) { 19 for ( ; pst != ped; *(pst++) = val); 20 } 21 22 int n, m; 23 int g[N][N]; 24 int f[N + 1][S]; 25 int cost[S]; 26 27 inline void init() { 28 scanf("%d%d", &n, &m); 29 for (int i = 0; i < n; i++) 30 for (int j = 0; j < n; j++) 31 g[i][j] = inf; 32 for (int i = 0, u, v, w; i < m; i++) { 33 scanf("%d%d%d", &u, &v, &w), u--, v--; 34 g[v][u] = g[u][v] = min(g[u][v], w); 35 } 36 } 37 38 int id[S]; 39 inline void solve() { 40 int S = (1 << n); 41 pfill(f[1], f[n + 1], inf); 42 pfill(cost, cost + S, inf); 43 for (int i = 0; i < n; i++) 44 id[1 << i] = i; 45 for (int i = 0; i < n; i++) 46 f[1][1 << i] = 0; 47 int ans = f[0][S - 1]; 48 for (int d = 2; d <= n; d++) { 49 for (int s = 0, val; s < S; s++) { 50 if ((val = f[d - 1][s]) == inf) 51 continue; 52 cost[0] = 0; 53 for (int ns = (s + 1) | s, cs, w, wc, cur; ns < S; ns = (ns + 1) | s) { 54 cs = (ns ^ s), w = cost[cs ^ (cs & (-cs))], wc = inf; 55 if (w == inf) 56 continue; 57 cur = id[(cs & (-cs))]; 58 for (int i = 0; i < n; i++) 59 if (s & (1 << i)) 60 wc = min(wc, g[cur][i]); 61 if (wc == inf) 62 continue; 63 f[d][ns] = min(f[d][ns], val + (w + wc) * (d - 1)); 64 cost[cs] = w + wc; 65 } 66 67 for (int ns = s; ns < S; ns = (ns + 1) | s) 68 cost[ns ^ s] = inf; 69 } 70 ans = min(ans, f[d][S - 1]); 71 } 72 printf("%d ", ans); 73 } 74 75 int main() { 76 init(); 77 solve(); 78 return 0; 79 }