# JZOJ 3737. 【NOI2014模拟7.11】挖宝藏(JZOJ 3737. [noi2014 simulation 7.11] treasure digging)-其他

## JZOJ 3737. 【NOI2014模拟7.11】挖宝藏(JZOJ 3737. [noi2014 simulation 7.11] treasure digging)

### $$\text{Solution}$$

$$h > 1$$ 时，考虑在每一层新建一个状态表示上一层宝藏全部挖完到这层某个点的答案

### $$\text{Code}$$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define RE register
#define IN inline
using namespace std;

const int N = 11, INF = 0x3f3f3f3f;
int h, n, m, a[N][N][N], f[N][N][N][1027], vis[N][N];
int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
struct point{int x, y;};
queue<point> Q;
struct treasure{int n, c[N][N];}b[N];
IN void Min(int &x, int y){x = min(x, y);}

IN void spfa(int z, int s)
{
while (!Q.empty())
{
point now = Q.front(); Q.pop();
for(RE int k = 0; k < 4; k++)
{
int x = now.x + fx[k][0], y = now.y + fx[k][1];
if (x > 0 && x <= n && y > 0 && y <= m && f[z][x][y][s] > f[z][now.x][now.y][s] + a[z][x][y])
{
f[z][x][y][s] = f[z][now.x][now.y][s] + a[z][x][y];
if (!vis[x][y]) vis[x][y] = 1, Q.push(point{x, y});
}
}
vis[now.x][now.y] = 0;
}
}
IN void Stenir_Tree(int z)
{
for(RE int s = 1; s < (1 << b[z].n); s++)
{
memset(vis, 0, sizeof vis);
for(RE int i = 1; i <= n; i++)
for(RE int j = 1; j <= m; j++)
{
for(RE int t = (s - 1) & s; t; t = (t - 1) & s)
Min(f[z][i][j][s], f[z][i][j][t] + f[z][i][j][s ^ t] - a[z][i][j]);
if (f[z][i][j][s] != INF) vis[i][j] = 1, Q.push(point{i, j});
}
spfa(z, s);
}
}

int main()
{
freopen("treasure.in", "r", stdin), freopen("treasure.out", "w", stdout);
scanf("%d%d%d", &h, &n, &m);
for(RE int i = 1; i <= h; i++)
for(RE int j = 1; j <= n; j++)
for(RE int k = 1; k <= m; k++) scanf("%d", &a[i][j][k]);
memset(f, INF, sizeof f), f[0][1][1][1] = 0, b[0].n = 1; int ans = INF;
for(RE int i = 1; i <= h; i++)
{
scanf("%d", &b[i].n), ++b[i].n;
for(RE int j = 2, x, y; j <= b[i].n; j++)
scanf("%d%d", &x, &y), b[i].c[x][y] = j, f[i][x][y][1 << j - 1] = a[i][x][y];
}
for(RE int i = 0; i <= h; i++)
{
Stenir_Tree(i);
if (i < h)
{
for(RE int j = 1; j <= n; j++)
for(RE int k = 1; k <= m; k++)
if (f[i][j][k][(1 << b[i].n) - 1] != INF)
Min(f[i + 1][j][k][1], f[i][j][k][(1 << b[i].n) - 1] + a[i + 1][j][k]);
}
else for(RE int j = 1; j <= n; j++)
for(RE int k = 1; k <= m; k++) Min(ans, f[h][j][k][(1 << b[h].n) - 1]);
}
printf("%d\n", ans);
}

————————

### $$\text{Solution}$$

When \ (H = 1 \), it is obviously Steiner tree board, and the most scheme must be tree
$$H & gt; 1$$, consider creating a new status on each floor, indicating that all the treasures on the previous floor have been excavated to a point on this floor
Homologous transfer

### $$\text{Code}$$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define RE register
#define IN inline
using namespace std;

const int N = 11, INF = 0x3f3f3f3f;
int h, n, m, a[N][N][N], f[N][N][N][1027], vis[N][N];
int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
struct point{int x, y;};
queue<point> Q;
struct treasure{int n, c[N][N];}b[N];
IN void Min(int &x, int y){x = min(x, y);}

IN void spfa(int z, int s)
{
while (!Q.empty())
{
point now = Q.front(); Q.pop();
for(RE int k = 0; k < 4; k++)
{
int x = now.x + fx[k][0], y = now.y + fx[k][1];
if (x > 0 && x <= n && y > 0 && y <= m && f[z][x][y][s] > f[z][now.x][now.y][s] + a[z][x][y])
{
f[z][x][y][s] = f[z][now.x][now.y][s] + a[z][x][y];
if (!vis[x][y]) vis[x][y] = 1, Q.push(point{x, y});
}
}
vis[now.x][now.y] = 0;
}
}
IN void Stenir_Tree(int z)
{
for(RE int s = 1; s < (1 << b[z].n); s++)
{
memset(vis, 0, sizeof vis);
for(RE int i = 1; i <= n; i++)
for(RE int j = 1; j <= m; j++)
{
for(RE int t = (s - 1) & s; t; t = (t - 1) & s)
Min(f[z][i][j][s], f[z][i][j][t] + f[z][i][j][s ^ t] - a[z][i][j]);
if (f[z][i][j][s] != INF) vis[i][j] = 1, Q.push(point{i, j});
}
spfa(z, s);
}
}

int main()
{
freopen("treasure.in", "r", stdin), freopen("treasure.out", "w", stdout);
scanf("%d%d%d", &h, &n, &m);
for(RE int i = 1; i <= h; i++)
for(RE int j = 1; j <= n; j++)
for(RE int k = 1; k <= m; k++) scanf("%d", &a[i][j][k]);
memset(f, INF, sizeof f), f[0][1][1][1] = 0, b[0].n = 1; int ans = INF;
for(RE int i = 1; i <= h; i++)
{
scanf("%d", &b[i].n), ++b[i].n;
for(RE int j = 2, x, y; j <= b[i].n; j++)
scanf("%d%d", &x, &y), b[i].c[x][y] = j, f[i][x][y][1 << j - 1] = a[i][x][y];
}
for(RE int i = 0; i <= h; i++)
{
Stenir_Tree(i);
if (i < h)
{
for(RE int j = 1; j <= n; j++)
for(RE int k = 1; k <= m; k++)
if (f[i][j][k][(1 << b[i].n) - 1] != INF)
Min(f[i + 1][j][k][1], f[i][j][k][(1 << b[i].n) - 1] + a[i + 1][j][k]);
}
else for(RE int j = 1; j <= n; j++)
for(RE int k = 1; k <= m; k++) Min(ans, f[h][j][k][(1 << b[h].n) - 1]);
}
printf("%d\n", ans);
}