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

\(\text{Solution}\)

当 \(h=1\) 时显然是斯坦纳树板子,最方案必然是树形的
\(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);
}