题目
选定一个起点 (S)，找到一棵生成树，最小化
[sum_{i=1}^n dep_i imes dis_i
]
(nleq 12)
分析
设 (dp[d][S]) 表示当前树中点的状态为 (S) ,并且树高为 (d) 的最小值，则
[dp[d][S_0|S_1]=min{dp[d-1][S_0]+d*f[S_0][S_1]},S_0cap S_1=empty
]
这个直接枚举子集可以做到 (O(n3^n))
再看两个集合互相连边最小值 (f)，这个可以通过枚举新的节点同样做到 (O(n3^n))
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=4096,M=12; int cho[N],b[N];
int two[M],dis[M][M],d[M],dp[2][N],f[N][N],n,m,al,ans;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed min(int a,int b){return a<b?a:b;}
signed main(){
n=iut(),m=iut(),al=(1<<n)-1,two[0]=1,ans=1e8;
if (n==1) return !putchar(48);
for (rr int i=1;i<n;++i) two[i]=two[i-1]<<1;
for (rr int i=0;i<n;++i) cho[two[i]]=i;
for (rr int i=0;i<n;++i)
for (rr int j=0;j<n;++j) dis[i][j]=1e8;
for (rr int i=1;i<=m;++i){
rr int x=iut()-1,y=iut()-1,w=iut();
dis[x][y]=dis[y][x]=min(dis[x][y],w);
}
for (rr int _S=0;_S<=al;++_S){
rr int S=al^_S,tot=0;
for (rr int j=0;j<n;++j) d[j]=1e8,dp[0][_S]=1e8;
for (rr int k=0;k<n;++k) if ((_S>>k)&1)
for (rr int j=0;j<n;++j) d[j]=min(d[j],dis[j][k]);
for (rr int j=S;j;) b[tot++]=j,j=(j-1)&S;
for (rr int j=tot-1;~j;--j)
f[_S][b[j]]=f[_S][b[j]&(b[j]-1)]+d[cho[-b[j]&b[j]]];
}
for (rr int i=0;i<n;++i) dp[0][two[i]]=0;
for (rr int i=1;i<n;++i){
for (rr int _S=0;_S<=al;++_S) dp[i&1][_S]=1e8;
for (rr int _S=1;_S<=al;++_S) if (dp[(i&1)^1][_S]<1e8){
rr int S=al^_S;
for (rr int j=S;j;j=(j-1)&S)
dp[i&1][_S^j]=min(dp[i&1][_S^j],dp[(i&1)^1][_S]+i*f[_S][j]);
}
ans=min(ans,dp[i&1][al]);
}
return !printf("%d",ans);
}