非常巧妙的 \(O(n^23^n)\) 做法。
题目的本质是要求一棵生成树,使得其每条边的长度与这条边的起点深度乘积的和最小。
我们使用状压 DP,考虑到当前状态与已经打通的点和深度有关,不妨设 \(f(S,x)\) 为当前所打通点集合为 \(S\),且当前树深度为 \(x\) 时的最小花费。状态转移方程
\[f(S,x)=\min_{S_0\subsetneq S}\left\{f(S_0,x-1)+x\sum_{u\in S \backslash S_0}\min_{v\in S_0}\{w(u,v)\}\right\}
\]
翻译成人话就是,枚举当前状态的真子集,作为第 \(x-1\) 层的状态,将真子集的补集作为当前 \(x\) 层的点,找到向第 \(x-1\) 层连边的最小花费之和(当然,还要保证 \(S_0\) 可以扩展到当前状态)。
初始:\(\forall 1\leq i\leq n,f(\{i\},0)=0\),其余为正无穷。目标:\(\min\limits_{1\leq i\leq n}\{f(U,i)\}\),其中 \(U\) 为全集。
其他需要注意的点:
现在分析一下复杂度。两两点枚举连边复杂度为 \(O(n^2)\),枚举所有子集的子集复杂度为 \(\sum\limits_{k=0}^{n}C^k_n2^k=(1+2)^n=3^n\)(二项式定理),于是总复杂度 \(O(n^23^n)\)。
(还在题解区发现 \(O(n3^n)\) 做法的,太巨了
#include <bits/stdc++.h>
using namespace std;
const int N=12,M=1<<N,INF=0x3f3f3f3f;
int n,m,d[N][N],f[M][N],g[M];
int main()
{
scanf("%d%d",&n,&m);
memset(d,INF,sizeof(d));
for(int i=0;i<n;++i) d[i][i]=0;
for(int i=1,a,b,c;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&c);
a--,b--; d[a][b]=d[b][a]=min(d[a][b],c);
}
for(int i=1;i<1<<n;++i)
for(int j=0;j<n;++j)
if(i>>j&1)
for(int k=0;k<n;++k)
if(d[j][k]!=INF)
g[i]|=1<<k; //预处理可扩展集合
memset(f,INF,sizeof(f));
for(int i=0;i<n;++i) f[1<<i][0]=0;
for(int i=1;i<1<<n;++i)
for(int j=i-1;j;j=(j-1)&i) //枚举真子集
if((g[j]&i)==i)
{
int cpl=i^j,cost=0; //cpl即是补集
for(int u=0;u<n;++u) //对于每个点,求最小
if(cpl>>u&1)
{
int tmp=INF;
for(int v=0;v<n;++v)
if(j>>v&1)
tmp=min(tmp,d[u][v]);
cost+=tmp;
}
for(int k=1;k<n;++k) f[i][k]=min(f[i][k],f[j][k-1]+k*cost); //更新
}
printf("%d",*min_element(f[(1<<n)-1],f[(1<<n)-1]+n));
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章