题目大意 给你$n$个点,$m$条边,要你选一个点作为根建一棵生成树满足代价最小
一棵生成树的代价是$\Sigma \; dep[i] * dis[fa_i][i]$, 其中$dep_i$表示$i$节点在这棵生成树中的深度（根节点深度为$0$,$dis[fa_i][i]$表示$i$节点到他父亲节点的距离
题目解析 首先通过$n\leq12$可以发现这是一道状压dp/搜索题
这里我们考虑状压dp
我们设状态$f[i]$表示选点的状态为$i$时,这棵生成树的最小代价,$st_{i,j}$表示当选点状态为$i$且$i$状态取最优方案时节点$j$的深度
那么我们可以很快想到一个dp方程
初始值满足$f_{2^s}=0,st_{2^s,s}=0$,其余位置的$f$和$st$都为$\mathrm{inf}$
这个方程的复杂度是$O(n^2 \times 2^n)$的
注意到根不是固定的, 所以我们可以每次选定一个根来进行dp的计算，总复杂度$O(n^3\times2^n)$
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> #define R register #define ll long long #define sum(a, b, mod) (((a) + (b)) % mod) const int MaxN = 13 ;int n, m;int g[MaxN][MaxN], st[1 << MaxN][MaxN], f[1 << MaxN];int dp (int s) memset (st, 0x3f , sizeof (st)), memset (f, 0x3f , sizeof (f)); int lim = (1 << n); f[1 << s] = 0 , st[1 << s][s] = 0 ; for (int i = 1 ; i < lim; i++) { if (f[i] < 0x3f3f3f3f ) { for (int j = 0 ; j < n; j++) { if (i & (1 << j)) { for (int k = 0 ; k < n; k++) { if (!(i & (1 << k))) { if ((g[j][k] != 0x3f3f3f3f ) && (f[i | (1 << k)] > f[i] + (g[j][k] * (st[i][j] + 1 )))) { f[i | (1 << k)] = f[i] + (g[j][k] * (st[i][j] + 1 )); memcpy (st[i | (1 << k)], st[i], sizeof (st[i | (1 << k)])); st[i | (1 << k)][k] = st[i][j] + 1 ; } } } } } } } return f[lim - 1 ]; } int main () scanf ("%d%d" , &n, &m); memset (g, 0x3f , sizeof (g)); for (int i = 1 ; i <= m; i++) { int u, v, d; scanf ("%d%d%d" , &u, &v, &d), --u, --v; g[u][v] = std ::min(g[u][v], d), g[v][u] = std ::min(g[v][u], d); } int ans = 0x3f3f3f3f ; for (int i = 0 ; i < n; i++) ans = std ::min(ans, dp(i)); printf ("%d\n" , ans); return 0 ; }