NOIP2017提高组day2 - T2：宝藏

题目链接

[NOIP2017 提高组] 宝藏

题目描述

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

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

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

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

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

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

输入格式

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

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

输出格式

一个正整数，表示最小的总代价。

样例 #1

样例输入 #1

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

样例输出 #1

4

样例 #2

样例输入 #2

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

样例输出 #2

5

提示

【样例解释 $1$】

小明选定让赞助商打通了 $1$ 号宝藏屋。小明开发了道路 $1\to 2$，挖掘了 $2$ 号宝藏。开发了道路 $1\to 4$，挖掘了 $4$ 号宝藏。还开发了道路 $4\to 3$，挖掘了 $3$ 号宝藏。

工程总代价为 $1\times 1+1\times 1+1\times 2=4$。

【样例解释 $2$】

小明选定让赞助商打通了 $1$ 号宝藏屋。小明开发了道路 $1\to 2$，挖掘了 $2$ 号宝藏。开发了道路 $1\to 3$，挖掘了 $3$ 号宝藏。还开发了道路 $1\to 4$，挖掘了 $4$ 号宝藏。

工程总代价为 $1\times 1+3\times 1+1\times 1=5$。

【数据规模与约定】

对于 $20\%$ 的数据： 保证输入是一棵树，$1\le n\le 8$，$v\le 5\times 10^3$ 且所有的 $v$ 都相等。

对于 $40\%$ 的数据： $1\le n\le 8$，$0\le m\le 10^3$，$v\le 5\times 10^3$ 且所有的 $v$ 都相等。

对于 $70\%$ 的数据： $1\le n\le 8$，$0\le m\le 10^3$，$v\le 5\times 10^3$。

对于 $100\%$ 的数据： $1\le n\le 12$，$0\le m\le 10^3$，$v\le 5\times 10^5$。

算法思想

根据题目描述，小明需要考虑如何开凿宝藏屋之间的道路，并且两个已经被挖掘过的宝藏屋之间的道路无需再开发，也就是说题目求的是一棵生成树，使得代价和最小。

由于开发一条道路的代价与道路的长度$L$和从起点到宝藏屋所经过的宝藏屋的数量（即宝藏屋的深度）$K$有关，因此不能使用最小生成树的算法进行计算。

考虑到结点数$n$的范围较小（$1\le n\le 12$），考虑使用状态压缩动态规划解决。

状态表示

用$S$表示当前生成树的状态，其二进制位上的$0$和$1$表示是否包含相应的宝藏屋。例如，当有$0、1、2、3、4$一共$5$个宝藏屋时，目前生成树已经包含了$0、3、4$，那么$state=(11001{)}_2$。$state$的范围从$0～2^n?1$。

状态除了跟当前生成树的情况有关，还与树的深度有关，用$i$表示当前生成树的深度，其中起点的深度为$0$。

因此，$f[state][i]$表示当前生成树状态为$state$、并且树的深度为$i$时，工程总代价的最小值。

最终结果为包含所有宝藏屋时，对于不同深度的生成树取最小值，即 m i n { f [ 2 n ? 1 ] [ i ] } min\{f[2^n-1][i]\} min{f[2n?1][i]}，其中$0\le i<n$。

状态计算

状态转移

要计算当前状态$f[state][i]$，从最后一步分析，即从第$i?1$层可以转移到第$i$层

• 不妨设第$i$层点集（宝藏屋）的状态为$s$，$s$是状态$state$的一个子集
• 如果前$i?1$层的点集的状态为$t$，那么 $t=state\oplus s$（异或运算$xor$）

因此：
f [ s t a t e ] [ i ] = m i n { f [ t ] [ i ? 1 ] + c o s t } f[state][i] = min\{f[t][i-1]+cost\} f[state][i]=min{f[t][i?1]+cost}

计算代价

其中$cost$表示第$i$层所有点（宝藏屋）到第$i?1$层的最小代价。那么$cost=L\times K$，其中$L$表示第$i$层所有点到第$i?1$层的长度之和；$K$代表从起点到第$i$的深度。

为了能够快速计算$L$，可以预处理得到任一点到所有集合的最小长度，不妨设$g[i][state]$表示点$i$到点集$state$的最小长度。那么$g[i][state]$等于点$i$到点集$state$中任意一点的最短距离。

算法流程

枚举所有要计算的点集$state$，在计算当前状态$f[state][i]$时：

• 要枚举$state$的所有子集，即第$i$层的点集状态$s$
  • 计算出第$i$层的所有点到第$i?1$层的最小长度之和$L$；
  • 然后再枚举深度$i$，计算$f[state][i]$

初始状态

• 求的是工程总代价最小值，因此$f$数组应初始化尽可能大
• 可以打通任意一个宝藏屋到地面的通道到，因此对于任意一点$i$，在生成树中只包含该点、且深度为$0$时，其最小值应该为$0$，即$f[1<<i][0]=0$

时间复杂度

时间复杂度包含两部分：

• 预处理$g[i][state]$的时间复杂度为$O(n^2\times 2^n)$
  • 状态数为$n\times 2^n$
  • 计算过程中需要枚举任意集合$state$中任意点，时间复杂度$O(n)$
• 计算状态$f[state][i]$的时间复杂度为$O(n^2\times 3^n)$
  • 计算过程中需要枚举集合的所有子集。考虑对于元素个数为$k$的子集，一共有$C_n^k$种情况，每个子集有$2^k$个子集，那么需要枚举的次数为${\sum }_{k=0}^n{C}_n^k\times 2^k$。利用二项式定理：${\sum }_{k=0}^n{C}_n^k\times 2^k=(1+2{)}^n=3^n$。
  • 对于每个子集需要 $n^2$次计算来算出剩余点到子集中的最小长度。

二项式定理$(x+y{)}^n=C_n^0{x}^n{y}^0+C_n^1{x}^{n?1}{y}^1+C_n^2{x}^{(}n?2)y^2+...+C_n^{n?1}{x}^1{y}^{n?1}+C_n^n{x}^0{y}^n$：

代码实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 12, M = 1 << N, INF = 0x3f3f3f3f;
//g[i][state]表示点i到集合state的最小长度
int w[N][N], g[N][M];
//f[state][i]表示当前生成树状态为state、并且树的深度为i时，工程总代价的最小值
int f[M][N];
int main()
{
    int n, m;
    cin >> n >> m;
    memset(w, 0x3f, sizeof w);
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        //点的编号从0开始，以便处理点集
        a --, b --;
        //有重边，所以取最小值
        w[a][b] = w[b][a] = min(w[a][b], c);
    }
    //预处理任一点到所有集合的最小长度
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < n; i ++)
        for(int state = 0; state < 1 << n; state ++)
            //枚举state中的点
            for(int k = 0; k < n; k ++)
                if(state >> k & 1)
                    //更新i到集合state长度的最小值
                    g[i][state] = min(g[i][state], w[i][k]); 
    //初始状态
    memset(f, 0x3f, sizeof f);
    //以i点为起点到达深度0的最小代价为0
    for(int i = 0; i < n; i ++) f[1 << i][0] = 0;
    //状态计算
    for(int state = 1; state < 1 << n; state ++)
    {
        //枚举state的子集s
        for(int s = state - 1 & state; s != 0; s = s - 1 & state)
        {
            //t表示前i-1层的点集状态
            int t = state ^ s, L = 0;
            //枚举第i层所有点，计算第i层的所有点到第i-1层的最小长度之和L
            for(int k = 0; k < n; k ++)
            {
                if(s >> k & 1) //点k在第i层的集合中
                {
                    L += g[k][t]; //累加最后一层所有点到上一层的长度
                    if(L >= INF) break; //点k到不了第i-1层的所有点
                }
            }
            
            if(L >= INF) continue; //子集s中存在点无法到达第i-1层
            //枚举深度，计算当前状态f[state][i]
            for(int i = 1; i < n; i ++)
                f[state][i] = min(f[state][i], f[t][i - 1] + L * i);
        }
    }
    //结果为包含所有宝藏屋时，对于不同深度的生成树取最小值
    int ans = INF;
    for(int i = 0; i < n; i ++)
        ans = min(ans, f[(1 << n) - 1][i]);
    cout << ans;
    return 0;
}