「NOIP 2017」宝藏

发表于 | | 阅读次数:
字数统计: 1.3k 字

Description

题目链接：Luogu 3959

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋， 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

赞助商决定免费赞助小明打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。

新开发一条道路的代价是：$L\times K$。其中 $L$ 代表这条道路的长度，$K$ 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

你需要求出小明挖掘出所有宝藏屋的最小代价。

数据范围：$1\le n\le 12$，$0\le m\le 1000$，$L\le 5\times 10^5$

Solution

我第一次看到这题时，差点以为是裸的 $\text{Prim}$！但是仔细分析了一波，发现层数对答案也是有影响的，直接贪心肯定是错误的。而直到我看到这个 $n\le 12$ 的数据范围，正解状压 $\text{DP}$ 也就呼之欲出了。

显然根据题意，挖掘的道路肯定会形成一棵树，那么我们可以按层数 $\text{DP}$。我们定义状态 $f[i][S]$ 表示当前距离根的深度为 $i$，已经打通了集合 $S$ 内的所有宝藏屋所需的最小花费。

考虑如何转移。首先枚举上一层的状态 $S$，令当前层的状态 $T$ 遍历 $S$ 的补集 $C$，转移方程即为：

其中 $\text{cost}$ 表示从集合 $S$ 内的宝藏屋开始打通集合 $T$ 内的宝藏屋的最小花费，可以在枚举 $S$ 后预处理得到。注意：当 $T$ 内的任何一个宝藏屋无法通过 $S$ 内的宝藏屋打通时，不能转移！

最终的答案为 $\min\{f[i][2^n-1]\}$（其中 $2^n-1$ 为全集）。

时间复杂度：$O(3^n\cdot n)$（复杂度证明见下文）

Code

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=15,M=1<<13;
const int inf=1<<30;
int n,m,dis[N],g[N][N],f[N][M];

void init() {
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) g[i][j]=inf;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i) f[1][1<<(i-1)]=0;
}
int main() {
    scanf("%d%d",&n,&m);
    init();
    for(int u,v,w;m--;) {
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=g[v][u]=std::min(g[u][v],w);
    }
    for(int S=0;S<(1<<n);++S) {
        for(int i=1;i<=n;++i) {
            dis[i]=inf;
            for(int j=1;j<=n;++j) if(S&(1<<(j-1))) dis[i]=std::min(dis[i],g[j][i]);
        }
        int C=((1<<n)-1)^S;
        for(int T=C;T;T=C&(T-1)) {
            int sum=0;
            bool ok=1;
            for(int i=1;i<=n;++i) if(T&(1<<(i-1))) {
                if(dis[i]==inf) {ok=0;break;}
                sum+=dis[i];
            }
            if(!ok) continue;
            for(int i=1;i<=n;++i) f[i][S|T]=std::min(f[i][S|T],f[i-1][S]+sum*(i-1));
        }
    }
    int ans=inf;
    for(int i=1;i<=n;++i) ans=std::min(ans,f[i][(1<<n)-1]);
    printf("%d\n",ans);
    return 0;
}

Complexity

顺便在这里证明一下子集的子集的个数是 $3^n$ 个吧！

二项式定理

推一波式子可以知道 $n$ 个数的子集个数为：

简单转化一下

根据二项式定理，即 $(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^k y^{n-k}$，可以得到原式即为

综上所述，$n$ 个元素的集合的子集的子集个数为 $3^n$。

通俗的证明

首先回忆一下子集的个数为 $2^n$ 个是如何证明的：每个数选或者不选有 $2$ 种状态，那么共有 $2^n$ 个子集。

那么我们模仿这个过程来证明子集的子集个数。对于 $n$ 个元素，设子集为 $S$，$S$ 的子集 $S’$，元素 $x$ 有以下状态：

  • $x\notin S$，自然 $x\notin S’$
  • $x\in S$，并且 $x\notin S’$
  • $x\in S$，并且 $x\in S’$

每个元素的状态有 $3$ 种，那么子集的子集个数为 $3^n$ 个。

0%