挖宝藏-程序员宅基地

在这里插入图片描述

在这里插入图片描述

Solution

这是一个较经典的斯坦纳树模型

就是把一堆点串起来的最小代价。
所以说最小生成树只是斯坦纳树的一个特殊情况.
所以我们可以设f[i][j][k][S]表示在当前(i,j,k)这个位置上,我们在同层已经选了集合为S的点的最小代价
方程可以写成 f [ i ] [ j ] [ k ] [ S ] = f [ i ] [ j ] [ k ] [ s ] + f [ i ] [ j ] [ k ] [ S − s ] − a [ i ] [ j ] [ k ] ; f[i][j][k][S]=f[i][j][k][s]+f[i][j][k][S-s]-a[i][j][k]; f[i][j][k][S]=f[i][j][k][s]+f[i][j][k][Ss]a[i][j][k];
这里要记录一下这个特殊的枚举子集的方法。
普通我们枚举子集都是直接先 2 n 2^n 2n再加上 2 n 2^n 2n的枚举就是 4 n 4^n 4n
但是斯坦纳树的枚举方法是每次把最后面的一个一去掉,然后再&一下原数,补回前面的1
具体代码是这样的

for (s=S&(S-1);s;s=S&(s-1))
						

Code

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

const long long maxn=10+1;
const long long maxs=1<<10;
const long long fx[4][2]={
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};

long long h,n,m,tot;
long long f[maxn][maxn][maxn][maxs];
long long a[maxn][maxn][maxn];
bool bz[maxn][maxn];
long long flag[maxn][maxn][maxn];
struct addr{
    
	long long x,y;
}d[maxn*maxn*800],b[maxn][maxn];
long long c[maxn];

void spfa(long long p,long long S){
    
	long long h=0,t=tot;
	while(h!=t){
    
		h=h%(maxn*maxn*maxn)+1;
		for (long long i=0;i<4;++i){
    
			long long xx=d[h].x+fx[i][0];
			long long yy=d[h].y+fx[i][1];
			if(xx<=n&&yy<=m&&xx>0&&yy>0)
				if(f[p][xx][yy][S]>f[p][d[h].x][d[h].y][S]+a[p][xx][yy]){
    
					f[p][xx][yy][S]=f[p][d[h].x][d[h].y][S]+a[p][xx][yy];
					if(!bz[xx][yy]){
    
						t=t%(maxn*maxn*maxn)+1;
						d[t]=(addr){
    xx,yy};
						bz[xx][yy]=1;
					}	
				}
		}
		bz[d[h].x][d[h].y]=0;
	}
}
	
int main(){
    
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%lld%lld%lld",&h,&n,&m);
	long long i,j,k;
	long long s,S;
	for (i=1;i<=h*n;++i)
		for (j=1;j<=m;++j)
			scanf("%lld",&a[(i-1)/n+1][(i-1)%n+1][j]);
	
	for (i=1;i<=h;++i){
    
		scanf("%lld",&c[i]);
		for (j=1;j<=c[i];++j){
    
			scanf("%lld%lld",&b[i][j].x,&b[i][j].y);
			flag[i][b[i][j].x][b[i][j].y]=j;
		}
		if(i>1) ++c[i];
	}
	
	memset(f,127,sizeof(f));
	long long ans=1e17;
	for (i=1;i<=h;++i){
    
		
		for (j=1;j<=n;++j)
			for (k=1;k<=m;++k)
				if(flag[i][j][k]) f[i][j][k][1<<(flag[i][j][k]-1)]=a[i][j][k];
				else f[i][j][k][0]=a[i][j][k];
		
		for (S=0;S<(1<<c[i]);++S){
    
			memset(d,0,sizeof(d));tot=0;
			memset(bz,0,sizeof(bz));
			for (j=1;j<=n;++j){
    
				for (k=1;k<=m;++k){
    
					for (s=S&(S-1);s;s=S&(s-1))
						if(f[i][j][k][s]<1e12&&f[i][j][k][S-s]<1e12)
							f[i][j][k][S]=min(f[i][j][k][S],f[i][j][k][s]+f[i][j][k][S-s]-a[i][j][k]);
					if(f[i][j][k][S]<1e12){
    
						d[++tot]=(addr){
    j,k};
						bz[j][k]=1;
					}
				}
			}
			spfa(i,S);
		}
		
		S--;
		for (j=1;j<=n;++j)
			for (k=1;k<=m;++k){
    
				if(f[i][j][k][S]>1e12) continue;
				if(i==h){
    
					ans=min(ans,f[i][j][k][S]);
				}
				else{
    
					if(flag[i+1][j][k]){
    
						f[i+1][j][k][1<<(c[i+1]-1)|1<<(flag[i+1][j][k]-1)]=f[i][j][k][S]+a[i+1][j][k];
					}
					else f[i+1][j][k][1<<(c[i+1]-1)]=f[i][j][k][S]+a[i+1][j][k];						
				}
			}
	}
	printf("%lld\n",ans);
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cdy1206473601/article/details/99536553

智能推荐

ThinkPHP 5 检测用户是否登录并根据权限调到页面_thinkphp5判断登录-程序员宅基地

需求:当用户没有登录时禁止评论或者创建某些东西 首先先要检测用户是否处于登录状态,没有的话需要先登录其实就是检测当前session 或者 cookie是否有值1.创建一个检测类注意:命名空间要正确 我当前目录如下 我在inde模块下新建一个behavior文件夹所以我的命名空间是namespace app\index\behavior;&lt;?phpnamespa..._thinkphp5判断登录

SQL 分组后取最小行号记录-程序员宅基地

本示例测试两个表联接查询后,分组并取分组后的最小行号记录 测试表: tb1表结构如下: CREATE TABLE [dbo].[tb1]( [a] [nvarchar](50) NOT NULL, [b] [nvarchar](50) NULL, [c] [nvarchar](50) NULL, CONSTRAINT [PK_tb1] PRIMARY ...

Python-while 计算100以内奇数和_python用while求1到100的奇数和-程序员宅基地

sum = 0n = 99while n > 0: sum = sum + n n = n - 2print(sum)只要条件满足,就不断循环,条件不满足时退出循环。比如我们要计算100以内所有奇数之和,可以用while循环实现:在循环内部变量n不断自减,直到变为-1时,不再满足while条件,循环退出。#100以内奇数的和(不包括100)sum = ..._python用while求1到100的奇数和

Forefront边缘防火墙版本比较-程序员宅基地

功能ISA 2004ISA 2006TMG 2010网络层防火墙YYY应用层防火墙YYYInternet访问保护(Web代理)YYYExchange Server(SMTP、POP3、IMAP4、OWA、OMA、Outlook AnyWhere)发布YYY网站发布YY

rtmp和http-flv推流及rtsp-server 区别及搭建提示_web rtsp rtmp server_Tombon的博客-程序员宅基地

这里写自定义目录标题rtmp和http-flv推流及rtsp-server 区别及搭建提示新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML 图表FLowchart流程图导出与导入导出导入rtmp和http-flv推流及rtsp-server 区别及搭建提示你好! 这是_web rtsp rtmp server

随便推点

xterm 的配置 _xterm-selection-程序员宅基地

/etc/X11/app-defaults/XTerm#XTerm*font: -misc-fixed-medium-r-normal--20-200-75-75-c-100-iso8859-1XTerm*font: -misc-fixed-medium-r-normal--18-120-100-100-c-90-iso10646-1XTerm*wideFont: -misc-fixed-medium-r-normal-*-18-120-100-100-c-180-iso10646-1XTer_xterm-selection

goland安装go.etcd.io/etcd/clientv3出现问题_etcd v3.3.27-程序员宅基地

问题描述:D:\gocode\src\etcd_demo\etcd>go getgithub.com/coreos/etcd/clientv3/balancer/resolver/endpoint…\pkg\mod\github.com\coreos\[email protected]+incompatible\clientv3\balancer\resolver\endpoint\endpoint.go:114:78: undefined: resolver.BuildOption…\pkg\mod_etcd v3.3.27

文件服务之ftp-程序员宅基地

一.什么是ftp?简介:ftp是(文件传输协议),是tcp/ip协议族中,应用层的一个协议。功能:提供客户机和服务器之间下载和上传文件。 服务器<---------------->客户机 文件从服务器传到客户机------下载 客户机把文件传到服务器-----上传程序:ftp对应的应用程序(软件包)vsftp端口在tcp传输层,用来标记程序,表示什么程序对外提供服务控制端口:21(验证用户名和密码的输入)数据端口:20(传数据...

vue核心插件之一 vue-router_v-router两个核心组件-程序员宅基地

1 安装vue-router1)官网上下载,通过src引入js文件2)npm 安装npm install vue-router2 router实现跳转,这里通过构建vue项目main.js主文件;App.vue文件;跳转的两个页面:hello.vue add HelloWorld.vue路由配置文件index.js1)main.js配置引入相应的文件..._v-router两个核心组件

Windows内核驱动开发入门学习资料_windows 驱动开发 百度网盘-程序员宅基地

Windows内核驱动开发入门学习资料一、书籍推荐《Windows驱动开发技术详解》作者:张帆、史彩成;出版社:电子工业出版社《天书夜读:从汇编语言到Windows内核编程》作者:谭文、邵坚磊;出版社:电子工业出版社《寒江独钓:Windows内核安全编程》作者:谭文、杨潇、邵坚磊;出版社:电子工业出版社其他驱动开发相关书籍二、源码学习《Windo_windows 驱动开发 百度网盘

KVM: Bare-Metal Hypervisor?-程序员宅基地

I need to turn to you, knowledgeable readers, for help in answering some questions. In a followup to yesterday'sannouncement by Red Hat about its virtualization roadmap, I asked the company some que