luogu3959NOIp2017宝藏题解--状压DP

题目链接

https://www.luogu.org/problemnew/show/P3959

分析

首先最后得到的一定是一颗生成树,从树高为h的节点x向深处扩展y的代价为(h+1) * dis(x,y)

我们以树高作为阶段,枚举已经扩展哪些节点的二进制状态x,又向深处扩展哪些节点的二进制状态y，设$f[dep][sta]$为已经挖到第dep层,当前已经挖了的宝藏用二进制表示下的状态为sta时的最小代价。状态转移方程为

$f[dep+1][x|y] = min(f[dep+1][x|y] , f[dep][x] + (dep+1) * cost(x,y))$,$y$满足$y$是$x$补集的子集

$cost(x,y)$是集合$x$扩展到集合$y$的最小距离,可以先通过计算点到集合的距离,再计算集合到集合的距离

这时候就有一个不怎么naive的问题,这个$x$到$y$的距离不一定就是$x$中最优情况下最深那一层,也就是dep层上的节点,而是可能是由其他层数上的节点连过来的,这样不又是不合法的转移吗?

这时候JYH大佬又跳了出来,说道:当前你这么不合法的枚举肯定比合法枚举不知道低到哪里去了(因为 * (dep+1)).而且层数是递增枚举的,枚举每一层时所有状态又会被枚举一遍,所以说你这个不是由最深层上的点扩展的状态一定在之前被枚举过,所以这么做是资瓷的

菜鸡RyeCatcher于是又开始%起了JYH这个OI又强还有妹子的巨佬

JYH巨佬很高兴又教了他几招:

1
2
3
for(ri s=sta;s;s=(s-1)&sta) //枚举sta子集

s= sta^U //获得sta补集

还教会他时间复杂度:

我们枚举了所有状态的补集的子集,相当于枚举了所有自己的子集

空集的子集只有一个 $C^0_N $

一个元素的子集有$C^1_N$个,这个又有$2^1$个子集

两个元素的子集有$C^2_N$个,这个又有$2^2$个子集

…

所有子集的子集个数就有$C^0_N \times 1 + C^1_N \times 2^1 + C^2_N \times 2^2 + … + C^N_N \times 2^N$

二项式定理可知这不就是$(2+1)^N$,加上钦定根节点和枚举层数,时间复杂度$O(3^N N^2)$

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=12;
const ll inf=1e17+19260817;
ll f[1<<12][13];
ll ss_dis[1<<12][1<<12],ps_dis[1<<12][13],g[13][13];//ps_dis 点到状态距离 ss_dis状态到状态最小距离
int n,m;
int U,C;
int main(){
    int x,y;ll z;
    ll ans=inf;
    read(n),read(m);
    U=1<<n;
    for(ri i=0;i<U;i++){
        for(ri j=0;j<U;j++)ss_dis[i][j]=inf;
        for(ri j=0;j<n;j++)ps_dis[i][j]=f[i][j]=inf;
    }
    for(ri i=0;i<n;i++){
        for(ri j=0;j<n;j++)if(i!=j)g[i][j]=inf;
    }
    for(ri i=0;i<m;i++){
        read(x),read(y),read(z);
        x--,y--; //注意要-1
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    for(ri i=0;i<n;i++){//枚举起点
        for(ri j=0;j<U;j++){//枚举状态
            for(ri k=0;k<n;k++){//枚举状态中的点
                if(j&(1<<k)){
                    ps_dis[j][i]=min(ps_dis[j][i],g[i][k]);                  
                }
            }
        }
    }
    for(ri i=0;i<U;i++){
        C=i^(U-1);//补集 注意是U-1
        for(ri j=C;j;j=(j-1)&C){//补集的子集
            z=0;
            for(ri k=0;k<n;k++){
                if(j&(1<<k)){
                  	if(dis[i][k]==inf)z=inf;
                    else z+=ps_dis[i][k];
                }
            }
            ss_dis[j][i]= (z>=inf)? inf:z;
        }
    }
    for(ri r=0;r<n;r++){//起点
        for(ri i=0;i<U;i++){
            for(ri j=0;j<n;j++)f[i][j]=inf;
        }
        f[1<<r][0]=0;
        for(ri d=0;d<n;d++){//树高或者层数
            for(ri i=0;i<U;i++){//子集
                C=i^(U-1); //注意是U-1
                if(f[i][d]==inf)continue;
                for(ri j=C;j;j=(j-1)&C){
                    if(f[i][d]==inf)continue;
                    f[i|j][d+1]=min(f[i|j][d+1],f[i][d]+1ll*(d+1)*ss_dis[j][i]);//注意由j到i
                }
            }
        }
        for(ri d=0;d<n;d++)ans=min(ans,f[U-1][d]);
    }
    printf("%lld\n",ans);
    return 0;
}