P3959 [NOIP 2017 提高组] 宝藏

#算法/进阶搜索
题目
参考题解

首先,我们看下数据,n最大为12,并且每两个结点都可以由上一个结点推出来,那么,我们可以考虑从状态压缩的角度考虑
设$f[i][j]$,其中,i代表深度,j代表状态,由于我们每次的状态都是由上一次的状态推导出来,所有这一层比上一层多余的状态(上一层没有被选,但这层被选的宝藏图)的消费就等于上一层到这一层的花费乘上深度.(乘上深度的原因是我们每一层的状态都是比从上一层推导而来的,所以,这一层的深度比上一层加1,那么,这一层新增的藏宝图到起点的距离也就比上一层多1)
预处理:
首先,定义g[i]代表i上所有位置处于1上的结点以及该点能遍历到的点

for(int i=0;i<(1<<n);i++){g[i]=i;for(int j=0;j<n;j++){if(((i>>j)&1)){for(int k=0;k<e[j+1].size();k++){g[i]|=(1<<(e[j+1][k].to-1));}}}}

接着,再定义数组cst[i][j]代表从状态i到j上多余的藏宝图的花费

  for(int i=0;i<(1<<n);i++){for(int j=0;j<(1<<n);j++){if(i==j)continue;//保证i!=jif((i|j)!=j)continue;//保证i是j的子集if((g[i]|j)==g[i])//保证状态i最终的状态包含j(j是g[i]的子集){pos[i][j]=1;//方便后序递推时候,可以直接判断两种状态能否相关推导for(int k=0;k<n;k++){int mi=1e9;//寻找i中没有,j中有的藏宝图if(!((i>>k)&1)&&((j>>k)&1)){for(int h=0;h<e[k+1].size();h++){int to=e[k+1][h].to;int w=e[k+1][h].w;if((i>>(to-1))&1){//当我们找到了这个藏宝图,我们再寻找这个藏宝图到i任意一个状态的最小值mi=min(w,mi);}}    cst[i][j]+=mi;}}}}}

最后将数组f[0][i],i为每个结点处于的位置全部定义为最大值,并从深度一开始,寻找能够将所有藏宝图找到的最小值

for(int i=0;i<=n;i++){for(int j=0;j<(1<<n);j++){f[i][j]=1e9;}}for(int i=0;i<n;i++){f[0][1<<i]=0;}for(int i=1;i<=n;i++){for(int j=0;j<(1<<n);j++){for(int k=0;k<(1<<n);k++){if(pos[j][k]==0)continue;if(f[i-1][j]==1e9)continue;f[i][k]=min(f[i][k],f[i-1][j]+i*cst[j][k]);}}}int ans=1e9;for(int i=0;i<=n;i++){ans=min(ans,f[i][(1<<n)-1]);}cout<<ans<<endl;