题目等价于给定无向图, 求一棵有根生成树, 假设树的根为$rt$, 对于树上的边$(u,v,w)$, 花费为$dep[v]*w$, 使得总花费最小.
设$dp[S][d]$为当前集合为$S$, 树的深度为$d$时的最小花费.
有$dp[S][d]=min{dp[S'][d-1]+cost[S'][S]}$
$S'$是$S$的子集, $cost$可以预处理, 总的复杂度是$O(n^22^n+n3^n)$
#include <iostream> #include <cstdio> #include <string.h> #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; const int N = 12, INF = 0x3f3f3f3f; int n, m, a[N][N]; int dp[1<<N][N], f[1<<N][N]; int c[1<<N][1<<N]; int main() { scanf("%d%d", &n, &m); memset(a,INF,sizeof a); REP(i,1,m) { int u,v,w; scanf("%d%d%d",&u,&v,&w); --u,--v; a[u][v]=a[v][u]=min(a[u][v],w); } int mx = (1<<n)-1; memset(f,INF,sizeof f); REP(s,1,mx) REP(i,0,n-1) if (s>>i&1) { f[s][i] = 0; REP(j,0,n-1) if (s>>j&1^1) f[s][j] = min(f[s][j], a[i][j]); } memset(dp,INF,sizeof dp); REP(i,0,n-1) dp[1<<i][0] = 0; REP(d,1,n-1) REP(i,1,mx) { for (int j=i-1&i; j; --j&=i) if (dp[j][d-1]!=INF) { if (!c[i][j]) { long long sum = 0; REP(k,0,n-1) sum += (i>>k&1)*f[j][k]; if (sum>=INF) c[i][j] = INF; else c[i][j] = sum; } if (c[i][j]==INF) continue; dp[i][d] = min(dp[i][d], dp[j][d-1]+c[i][j]*d); } } int ans = INF; REP(i,0,n-1) ans = min(ans, dp[mx][i]); printf("%d ", ans); }