[NOIP2017 D2 T2]宝藏（状压dp）

发表于 更新于 分类于 ，
NOIP2017 Day2 T2 treasure

题目

描述

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋， 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
$$ L \times K $$
$L$代表这条道路的长度，$K$代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

输入

第一行两个用空格分离的正整数 $n$ 和 $m$，代表宝藏屋的个数和道路数。

接下来 $m$ 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 $1$~$n$），和这条道路的长度 $v$。

输出

输出共一行，一个正整数，表示最小的总代价。

样例输入

样例输入1

1
2
3
4
5
6
4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 1

样例输入2

1
2
3
4
5
6
4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 2

样例输出

样例输出1

1
4

样例输出2

1
5

数据规模与约定

对于 20% 的数据： 保证输入是一棵树，$1 \le n \le 8$ , $v \le 5000$ 且所有的 v 都相等。
对于 40% 的数据： $1 \le n \le 8$，$0 \le m \le 1000$ , $v \le 5000$ 且所有的 v 都相等。
对于 70% 的数据： $1 \le n \le 8$，$0 \le m \le 1000$，$v \le 5000$
对于 100% 的数据： $1 \le n \le 12$，$0 \le m \le 1000$ , $v \le 500000$

解题思路

首先，很容易发现打通后的道路一定是一棵树，并且，若以起点为根并令其深度为$0$，则题目中的 $K$ 即为这条路所连向的点的深度。

观察数据范围，$n \le 12$，显然是状压dp：

  • dp状态：$dp[i][S]$ 表示考虑到树的第$i$层，前$i$层已选的点的集合为$S$（二进制状压）的最小代价。
  • dp方程（刷表法）：
    已知$dp[i][S]$时，可枚举所有由不在$S$中的点构成的集合作为第$i+1$层，则状态转移为$$dp[i][S] \to dp[i+1][S|S’] + (i+1) \times \Sigma \ min{G[a][b]|a \in S , b \in S’,S \cap S’ = \emptyset }$$
    简单一点，就是$$dp[i][S] \to dp[i+1][S|S’] + (i+1) \times sval[S’][S] }$$
    其中$sval[A][B]$表示集合A到集合B的最短距离，即集合A中所有点到集合B的最短距离之和。可以先预处理出每个点到每个集合的最短距离$pval[i][S]$（也就是点$i$到集合$S$中所有点的距离的最小值），然后用$pval[i][B]$更新$sval[A][B]$。
  • dp顺序：由dp方程可得：从小到大枚举层数，再枚举集合即可
  • 边界条件：枚举根节点，设为$root$，则$dp[0][1<<(root-1)] = 0$

状压相关技巧

  • 若$S$是$U$的子集，则$S$关于$U$的补集：$S ^\wedge U$
  • 判断点$k$是否在集合$S$中（即$S$的第$k-1$位是否为$1$）：S & (1 << (k-1)) ！= 0 ? "Yes" : "No";
  • 枚举$S$的子集：for(int i = S; i; i = (i - 1) & S){...}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# include<cstdio>
# include<algorithm>

using namespace std;

typedef long long LL;

const int INF = 1e7;
const int N = 13;
int n, m, g[N][N], u, v, p, U;
LL dp[N][1<<N], ans = 1e14, sval[1<<N][1<<N], pval[N][1<<N];

void init(int root){
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= U; j++)
            dp[i][j] = INF;
    dp[0][1<<(root-1)] = 0;
}

int main(){
    scanf("%d%d", &n, &m);
    U = (1 << n) - 1;
    for(int i = 1; i <= n; i++)				//initialize g[i][j]
        for(int j = 1; j <= n; j++)
            if(i ^ j)
                g[i][j] = INF;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= U; j++)
            pval[i][j] = INF;
    for(int i = 0; i <= U; i++)
        for(int j = 0; j <= U; j++)
            sval[i][j] = INF;
    while(m--){
        scanf("%d%d%d", &u, &v, &p);
        g[u][v] = min(g[u][v], p);
        g[v][u] = min(g[v][u], p);
    }
    for(int i = 1; i <= n; i++)				//initialize pval[i][S]
        for(int j = 0; j <= U; j++)
            for(int k = 1; k <= n; k++)
                if(j & (1 << (k - 1)))
                    pval[i][j] = min(pval[i][j], 1ll*g[i][k]);
    for(int i = 0; i <= U; i++){			//initialize sval[A][B]
        int C = i ^ U;
        for(int s = C; s; s = (s - 1) & C){
            LL temp = 0;
            for(int j = 1; j <= n; j++)
                if(s & (1 << (j - 1)))
                    temp += pval[j][i];
            sval[s][i] = temp >= INF ? INF : temp;
        }
    }
    for(int root = 1; root <= n; root++){	//dp
        init(root);
        for(int i = 0; i < n; i++)
            for(int S = 0; S <= U; S++)
                if(dp[i][S] != INF){
                    int C = S ^ U;
                    for(int s = C; s; s = (s - 1) & C)
                        dp[i+1][S|s] = min(dp[i+1][S|s], dp[i][S] + (i + 1) * sval[s][S]);
                }
        for(int i = 0; i < n; i++)	ans = min(ans, dp[i][U]);
    }
    printf("%lld", ans);
    return 0;
}