洛谷 P3959 NOIp2017提高组 宝藏 题解【状态压缩】【DP】【生成树】【贪心】

点击量：240

    还是在NOIp2018前写出了这道2017谜之状压。

目录

问题描述

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

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

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

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

新开发一条道路的代价是：

这条道路的长度×从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

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

输入格式

输入文件名为treasure.in。

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

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

输出格式

输出文件名为treasure.out。

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

输入输出样例

输入输出样例1

treasure.in	treasure.out
4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 1	4

输入输出样例1说明

小明选定让赞助商打通了\(1\)号宝藏屋。小明开发了道路\(1\rightarrow 2\)，挖掘了\(2\)号宝藏。开发了道路\(1\rightarrow 4\)，挖掘了\(4\)号宝藏。还开发了道路\(4\rightarrow 3\)，挖掘了\(3\)号宝藏。工程总代价为：

\[\ \ \ \ \ \ \ 1\times 1+1\times 1+1\times 2=4\\
(1\rightarrow 2) (1\rightarrow 4) (4\rightarrow 3)\]

输入输出样例2

treasure.in	treasure.out
4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 2	5

输入输出样例2说明

小明选定让赞助商打通了\(1\)号宝藏屋。小明开发了道路\(1\rightarrow 2\)，挖掘了\(2\)号宝藏。开发了道路\(1\rightarrow 3\)，挖掘了\(3\)号宝藏。还开发了道路\(1\rightarrow 4\)，挖掘了\(4\)号宝藏。工程总代价为：

\[\ \ \ \ \ \ 1\times 1+3\times 1+1\times 1 = 5\\
(1\rightarrow 2) (1\rightarrow 3) (1\rightarrow 4) \]

数据规模与约定

对于\(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\)

题解：

    数据范围这么小，不是搜索就是状压，不过更像搜索一点，dfs大力剪枝可以通过，一般写得好的dfs暴力也能拿70分。

    这个题题意是要找一棵生成树，使得每条边的权值乘上其父亲节点的深度的和最小（根节点深度为\(1\)）。

    首先我想到了一种三进制状压，分别用\(0,1,2\)来存“不在树上的点”，“在树上但不是最深的点”，“在树上且为最深的点”，但是我们又要枚举更多的状态，而且三进制无法直接进行位运算，只能作为待选方案。

    实际上“在树上且为最深的点”这一状态是没有必要的，根据贪心，如果当前在树上不是最深的点需要扩展，一定会当它之前作为最深的点的状态就转移了，所以可以当作每个点都是最深的点。

    假设在这个图中，根节点为\(1\)，深度为\(3\)，我们如果此时用\(2\)号节点转移，一定不是最优的，因为无论用哪个节点转移，此时的代价系数都是\(3\)。而如果\(2\)号节点可以在树的深度为\(2\)时转移出一个更优的答案，这个答案就会用\(2\)的系数去更新另一个状态，因此最优状态是一定存在的，但是在转移的过程中无法确定哪个状态最优，因为还没有到DP的终点，所以所有可能的状态都要转移，这也是DP的魅力所在。

“即使自己不是最优状态也要为转移做出一点贡献。”

——沃兹·基硕·德

    然后我们开始DP转移，在填表法中，每个状态的来源都一定是它的子集（有些写法不一定是非空的），因此我们要枚举子集，例如当\(1101111_{(2)}\)从\(1000100_{(2)}\)转移过来时，需要用\(O(n^2)\)的时间去枚举新出现的\(1\)是从原来的哪个\(1\)转移过来的，实际上这个枚举只需要\(O(n)\)，因为每个点可以预处理出当转移来源为\(S\)时的最小转移边，此时只需要枚举新出现的\(1\)即可。

    此时讨论复杂度。对于子集个数和的计算，有\(\sum_{i=1}^{n}C_n^i\cdot 2^i\)，这个东西根据二项式定理(?)大致推出来是\(3^n\)的，也就是说\(4^n\)是一个很松的上界。同时我们枚举了\(n-1\)层树，以及\(n\)个新出现\(1\)的转移，总时间复杂度是\(O(3^n\times n^2)\)。

    枚举子集有一个技巧，我写在了置顶帖里，感觉比搜索什么的好用多了。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using std::min;
int f[12][1<<12];//dp数组
int dis[13][13];//点直接距离
int trans[13][1<<12];
int main()
{
    memset(dis,0x3f,sizeof(dis));
    memset(trans,0x3f,sizeof(trans));
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v]=min(dis[u][v],w);//注意去重
        dis[v][u]=min(dis[v][u],w);
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i)
        f[0][1<<i]=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<(1<<n);++j)
            for(int k=1,_j=j;k<=n;++k,_j>>=1)//预处理各种状态
                if(_j&1)
                    trans[i][j]=min(trans[i][j],dis[k][i]);
    for(int i=1;i<n;++i)
        for(int j=1;j<(1<<n);++j)
            for(int k=j;k;k=j&(k-1))
            {
                int tmp=0;
                for(int p=1,_j=j^k;p<=n;++p,_j>>=1)
                    if(_j&1&&tmp<inf)
                        tmp+=trans[p][k];//直接调用
                if(tmp<inf)//这里<inf是怕爆int，实际上开long long会安全一些
                    f[i][j]=min(f[i][j],f[i-1][k]+i*tmp);
            }
    int ans=inf;
    for(int i=0;i<n;++i)
        ans=min(ans,f[i][(1<<n)-1]);
    printf("%d\n",ans);
    return 0;
}