[NOIp2017]宝藏题解

非常巧妙的 (O(n^23^n)) 做法。
题目的本质是要求一棵生成树，使得其每条边的长度与这条边的起点深度乘积的和最小。
我们使用状压 DP，考虑到当前状态与已经打通的点和深度有关，不妨设 (f(S,x)) 为当前所打通点集合为 (S)，且当前树深度为 (x) 时的最小花费。状态转移方程

[f(S,x)=min_{S_0subsetneq S}left{f(S_0,x-1)+xsum_{uin S ackslash S_0}min_{vin S_0}{w(u,v)} ight} ]

翻译成人话就是，枚举当前状态的真子集，作为第 (x-1) 层的状态，将真子集的补集作为当前 (x) 层的点，找到向第 (x-1) 层连边的最小花费之和（当然，还要保证 (S_0) 可以扩展到当前状态）。
初始：(forall 1leq ileq n,f({i},0)=0)，其余为正无穷。目标：(minlimits_{1leq ileq n}{f(U,i)})，其中 (U) 为全集。
其他需要注意的点：

预处理出每个点能拓展出的集合。
为方便位运算，将所有点标号为 (0,dots,n-1)。

现在分析一下复杂度。两两点枚举连边复杂度为 (O(n^2))，枚举所有子集的子集复杂度为 (sumlimits_{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;
}

[NOIp2017]宝藏 题解

[NOIp2017]宝藏题解