___new2zy___ 的博客

___new2zy___ 的博客

题解 P3959 【宝藏】

posted on 2018-09-12 11:58:38 | under 题解 |

题解 P3959 【宝藏】

题目传送门:

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

话说。。。考场上真的想不到啊。。。(说白了就是菜)

我也是2017年入的OI坑,可是当时太菜了,以至于现在才写这题

本题主要考查:状压+dfs

也可以算是一道状压好(入门)


算法构建与设计:

话说。。。这题不应该先看数据范围的么(逃

我们发现,题目中明确:

对于100%的数据,1<=n<=12

以我们学习OI的经验,这题肯定是个状态压缩(状压)

(因为数据范围小到屈指可数啊)

那么,什么是状压呢?

听起来高大上,其实没什么

下面讲一讲我自己的理解吧(应该有专业术语的,可是我懒,不想度娘)

状压,即状态压缩的简称,是一种(在数据范围较小的情况下)将每个物品或者东西选与不选的状态“压”成一个整数的方法

通常我们采用二进制状压法,(对于二进制状压)即对于一个我们“压”成的状态,这个整数在二进制下中的1表示某个物品已选,而0代表某个物品未选,这样我们就可以通过枚举这些“压”成的整数来达到枚举所有的物品选与不选的总情况,通常我们称这些情况叫做子集,对于这个状态整数,通常设为s

(对于二进制状压)通过二进制下的位运算来达到判断某个物品选与不选的情况,再通过这个状态来进行一些其他的扩展,所以状压能简化我们对于问题的求解方式

而状压dp正是用到了这一点,通过一个状态来表示整体情况,对于这个情况进行一些最优化操作,最终达到求得全局最优解的目的

在这里,状压dp需要用到一些位运算的知识,下面给出一张图说明

那么有了这些位运算的法则,我们就可以快速判断一个东西在状态s中是否处于选或不选的状态,便于我们对于状态的更新与某一位的判断

(笔者的语句可能有些粗糙,理解大意即可,毕竟本人理解可能不太到位)

然而还有其他的状压方法,例如三进制状压法等等,本人在此就不再赘述

(其实是太菜不会讲,应该把机房某dalao拉过来讲一下的)

然而对于状压dp,本质上是与dp无异的

说白了,状压dp,没有改变dp本质的优化方法,阶段还是要照分,状态还是老样子,决策依旧要做,转移方程还是得列,最优还是最优,无后性还是无后性,所以它还是比较好理解的。


本题解决:状压dp

其实上面一段话,正包含了本题的解法:状压dp

(要不然我也不会讲那么多)

我们顺利想到了状压,但是问题又来了:如何进行dp呢

我们不妨先来一步一步分析题目所给条件:

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

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

哦,这是在说这是个有n个点的图,并且起点任意,有m条边

    3.已经开凿出的道路可以任意通行不消耗代价。
    每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路
    所能到达的宝藏屋的宝藏。

    另外,小明不想开发无用道路,
    即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

哦,这是在说已经访问过的节点之间不能再次连边,凡是能到达的节点的宝藏,小明都会得到(话说不会被人赶走么)(逃

    4.新开发一条道路的代价是:L*K
    L代表这条道路的长度,
    K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量
    (包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋) 。

哦,这是告诉了我们*连边的代价,为LK**(意义如上所述)

那么最后要求什么呢?

    5.请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,
    使得工程总代价最小

那么到了这里,我们可以总结出一句话题意

请选择合适的方案,满足已经属于同一个联通块中的两点间不会有直接相连的第二条边,
同时给定两点间连边的代价,为L*K 
试求在花费最少代价的情况下使得最终所有节点在同一个联通块中
(L*K为起点到当前点的所经过的节点数乘当前边长度)

哦,明白了,其实就是找到一个连边的顺序,最终使得所有点联通同时总代价最小

那么这其中一定存在着对于每个点选或不选的状态,正好可以用上面的状压解决

我们不妨设f[s]表示状态s下,使得这些选择的点在同一个联通块中的最小代价

那么,显然有如下的转移方程:(从i点转移到j点)

*f[1<<(j-1)|s]=f[s]+dis[i]G[i][j]**

其中G[i][j]表示i,j两点间道路的距离,dis[i]表示距离i根节点间的节点数

(如果你状压学的很好的话上面的方程就不用我解释了)(逃

既然需要求出最优解,那么我们当然需要用到搜索的思想,枚举每一个点是否被选用dfs实现

但是又因为这张图的起点不固定,不过没关系,我们只需要以每个点为根都进行一次dfs+状压dp就行了

到了这里,其实本题也就迎刃而解了

可能本人的思维有点跳跃,请见谅(本来是就菜,语言表达不太到位)

下面放代码

PS:代码里也有解释哦

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<3)+(p<<1)+c-'0';c=getchar();}
    return f*p;}
const int maxn=14;
int n,m,G[maxn][maxn],ans=inf;
int dis[maxn],f[1<<maxn];
//f[s]表示状态s下所花费的最小代价 
inline void dfs(int s)//对于状态s进行深搜 
{
    for(int i=1;i<=n;i++)
        {
            if(1<<(i-1)&s)//如果选过i 
                {
                    for(int j=1;j<=n;j++)
                        {
                            if(!(1<<(j-1)&s)&&G[i][j]!=1061109567)
                            //没有选过j而且i与j之间有连边 
                                {
                                    if(f[1<<(j-1)|s]>f[s]+dis[i]*G[i][j])//存在更优解 
                                        {
                                            int old_val=dis[j];//记录原dis值 
                                            dis[j]=dis[i]+1;
                                            f[1<<(j-1)|s]=f[s]+dis[i]*G[i][j]; 
                                            dfs(1<<(j-1)|s);//更新dp值,继续深搜下一步 
                                            dis[j]=old_val;//回溯 
                                        }
                                }
                        }
                }
        }
}
int main()
{
    n=read(),m=read();
    memset(G,0x3f,sizeof(G));
    for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),w=read();
            G[x][y]=G[y][x]=min(G[x][y],w);
            //多条边就取min 
        }
    for(int i=1;i<=n;i++)
        {
            memset(dis,0x3f,sizeof(dis));
            memset(f,0x3f,sizeof(f));
            dis[i]=1;//重置图,以i为起点出发,开始宝藏屋数为1 
            f[1<<(i-1)]=0;//初始状态代价为0 
            dfs(1<<(i-1));//状压dp+dfs 
            ans=min(ans,f[(1<<n)-1]);//更新答案(满状态时) 
        }
    printf("%d\n",ans);
    return 0;
}

$upd$:$2018$年$11$月$6$日

本来是在复习$NOIp$的,脑袋一热来看往年的题

结果发现我之前写的宝藏这题的题解竟然被人$hack$了。。。

于是乎开始修锅。。。修了一上午终于改对了$qwq$

请见讨论区 @余越 提出的$hack$数据链接

或者这个:hack数据

谢谢您们!

话说CCF的数据真心水

咳咳。。。先来看一下修完锅之后的想法

看到 @余越 提出的问题之后我想了半天,为什么会错掉呢?明明状态转移方程都是没错的,但为什么会输出$1046$而不是$1043$呢?

拉来了同机房的一位巨佬一起讨论了半天,发现真的是有问题的

在上面的做法中,状压之后的状态只记录了点集$s$表示哪些点被选择过,而可能会出现这样的情况:一个点在深度为$dep1$的时候更新了一个状态$s1$,而该点在深度为$dep2$的时候也更新了状态$s1$,但是这二者之间不是独立的,换句话说就是$dp$时产生了后效性,是错误的

那么正如 @余越 所说,“中间"存在更优解"的那一行的优化是不正确的,忽略了不同的$dis$取值对后续搜索的影响。”所以单独记录一个点集而不记录每个点在该点集中的深度状态是不完整的,所以我们要改进状态,消除后效性

定义状态$f[x][s][K]$表示点$x$在点集$s$中深度为$K$时的最小总代价

显然目标状态为$s==(1<<n)-1$时的最小代价,最终$x$和$K$无所谓

那么此时我们就可以写出改进后的转移方程:

$f[x][1<<(x-1)|s][K]=min(sum+dis[y]*G[y][x])$

发现$K$是没有实际意义的,它只是记录了x$点在$s$中的深度 而$sum$是上一层的最优解,$y$是上一层与$x$之间有连边的点 改进转移之后发现这个过程**更像深搜而不是状压** 这里的$s$只是起到了一个记录集合的作用,也并没有实际意义 但是这样记录之后,你会发现上面的$hack$数据过掉了 $Why?$ 因为我们这样记录之后,每个点在点集中的深度就已经记录了 换句话说,这样就**消除了不同深度对$dp$状态的影响,消除了后效性** 此时的时间复杂度为$O(nn^22^n)=O(n^3*2^n)$比较慢呀$qwq$ 可能上面我说得有点扯。。。感性理解一下吧$\text {QAQ}$ 下面发一个改完之后的代码: ```cpp #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> using namespace std; typedef long long ll; const int inf=2e9+7; inline int read() { int p=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){p=(p<<3)+(p<<1)+c-'0';c=getchar();} return f*p;} const int maxn=15; int n,m,lim,ans=inf,G[maxn][maxn]; int dis[maxn],f[maxn][1<<maxn][maxn]; // inline void dfs(int s,int sum,int dep) //s表示现在的点集,sum记录最优解,dep代表层数 { if(sum>=ans)return ;//最优性剪枝 if(s==lim)return (void)(ans=sum); for(int i=1;i<=n;i++) { if(!(1<<(i-1)&s))continue; for(int j=1;j<=n;j++) { if(!(1<<(j-1)&s)&&G[i][j]<1e9) { if(f[j][1<<(j-1)|s][dep+1]<=sum+dis[i]*G[i][j])continue; f[j][1<<(j-1)|s][dep+1]=sum+dis[i]*G[i][j]; dis[j]=dis[i]+1; dfs(1<<(j-1)|s,f[j][1<<(j-1)|s][dep+1],dep+1); } } } } int main() { n=read(),m=read(),lim=(1<<n)-1; memset(G,0x3f,sizeof(G)); for(int i=1;i<=m;i++) { int x=read(),y=read(),w=read(); G[x][y]=G[y][x]=min(G[x][y],w); } for(int i=1;i<=n;i++) { memset(dis,0,sizeof(dis)); memset(f,0x3f,sizeof(f)); dis[i]=1,dfs(1<<(i-1),0,0); } printf("%d\n",ans); return 0; } ``` 再次感谢 @余越 指出算法的错误,谢谢您! ---- 这题大概算是状压$dp$+$dfs$的经典题了吧 顺便推广一下自己写的状压$dp$复习博客:浅谈一类dp问题----状压dp

(感觉自己能上日报)

有什么意见和建议可以发评论或者私信我,如果有仍需要改善的地方我会尽快改正的

最后,感谢你的阅读!

无耻的推一发我的blog:

https://www.luogu.org/blog/new2zy/

拜拜~~~