JZOJ 3737. 【NOI模拟7.11】挖宝藏(treasure)

DescriptionDescriptionDescription

求在一张立体h×n×mh\times n\times mh×n×m的图中将一些点连在一起的最小花费，第iii层有gsigs_igsi​个点

数据范围： h,n,m≤11,gsi≤9h,n,m\leq 11,gs_i\leq 9h,n,m≤11,gsi​≤9

SolutionSolutionSolution

斯坦纳树模板题

注意设出来的dpdpdp是有后效性的，由于方程满足三角形不等式，所以可以用spfaspfaspfa转移

对于三维的情况，多设一个点表示每个点都必须选即可

时间复杂度：O(hnm210)O(hnm2^{10})O(hnm210)

CodeCodeCode

#pragma GCC optimize(2)#include<queue>#include<cstdio>#include<cctype>#include<cstring>#define LL long long#define INF 2000000000using namespace std;int h,n,m;int gs[11],bz[11][11][11];LL a[11][11][11],ans=0x3f3f3f3f3f3f3fll,f[11][11][11][1024];const short dx[4]={-1,0,1,0};const short dy[4]={0,1,0,-1};inline void MIN(LL &a,LL b){if(b<a)a=b;return;}inline LL read(){LL f=0,d=1;char c; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;}struct node{int x,y;};queue<node>q;bool vis[11][11];inline void spfa(int i,int S){while(q.size()){node u=q.front();q.pop();for(register int k=0;k<4;k++){int x=u.x+dx[k],y=u.y+dy[k];if(x<1||y<1||x>n||y>m) continue;if(f[i][x][y][S]>f[i][u.x][u.y][S]+a[i][x][y]){f[i][x][y][S]=f[i][u.x][u.y][S]+a[i][x][y];if(!vis[x][y]) vis[x][y]=true,q.push((node){x,y});}}vis[u.x][u.y]=false;}return;}signed main(){freopen("treasure.in","r",stdin);freopen("treasure.out","w",stdout);h=read();n=read();m=read();for(register int i=1;i<=h;i++)for(register int j=1;j<=n;j++)for(register int k=1;k<=m;k++)a[i][j][k]=read();for(register int i=1;i<=h;i++){gs[i]=read();for(register int j=1,x,y;j<=gs[i];j++) {x=read();y=read();bz[i][x][y]=j;}if(i>1) gs[i]++;}memset(f,127,sizeof(f));for(register int i=1;i<=h;i++){for(register int j=1;j<=n;j++)for(register int k=1;k<=m;k++)if(bz[i][j][k]) f[i][j][k][1<<(bz[i][j][k]-1)]=a[i][j][k];else f[i][j][k][0]=a[i][j][k];for(register int S=0;S<(1<<gs[i]);S++){for(register int j=1;j<=n;j++)for(register int k=1;k<=m;k++){for(register int T=S&(S-1);T;T=S&(T-1))if(f[i][j][k][T]<INF&&f[i][j][k][S-T]<INF)MIN(f[i][j][k][S],f[i][j][k][T]+f[i][j][k][S-T]-a[i][j][k]);if(f[i][j][k][S]<INF) q.push((node){j,k}),vis[j][k]=true;}spfa(i,S);if(S+1==(1<<gs[i])){for(register int j=1;j<=n;j++)for(register int k=1;k<=m;k++){if(f[i][j][k][S]>INF) continue;if(i==h) MIN(ans,f[i][j][k][S]);else if(bz[i+1][j][k]) f[i+1][j][k][(1<<(gs[i+1]-1))|(1<<(bz[i+1][j][k]-1))]=a[i+1][j][k]+f[i][j][k][S];else f[i+1][j][k][(1<<(gs[i+1]-1))]=a[i+1][j][k]+f[i][j][k][S];}}}}printf("%lld",ans);}