【题解 nkoj8145 动物巧克力】

$\texttt{Description}$

给定一个 $n\times m$ 的矩阵，每个格子有一个数 $c_{i,j}$，如果这个数为 $-1$ 表示这个格子不能选。选出尽量少的连着的格子使其含有至少 $k$ 个互不相同的数。无解输出 $-1$。

$\texttt{Data Range:}1\le n\times m\le 233,1\le k\le 5,1\le c_{i,j}\le n\times m$

$\texttt{Solution}$

之所以写这篇题解，是因为这个题涉及到一个非常重要的技巧。

首先如果 $c_{i,j}$ 非常的小，那这就是个朴素的斯坦纳树。

但是这题 $c_{i,j}$ 很大，怎么办？

因为我们只要求选出 $k$ 个互不相同的数，所以考虑对这些格子的数进行染色，例如两个格子的数分别是 $2,3$，而数字 $2,3$ 染的颜色相同，那么这两个格子的数被我们认为是相同的。

染色的方案数是第二类斯特林数，这你不T飞我请你吃火锅（（（

然后文首提到的“非常重要的技巧”就派上用场了——对，就是随机化乱搞！

其实也不是完全地乱搞，因为手算可得这题单次随机染色得到正解的概率足够支撑我们随机 $200$ 次左右得到最优解。

我把随机次数选成了 $150$，A了后发现 $125$ 次随机都不行，看来这个 $150$ 次随机在死亡的边缘反复衡跳啊（（（

考场上的随机次数当然是卡着时间了，所以单次随机的常数特别重要，随机次数加上 $20\%$ 也会大大提升正确率（

果然乱搞总是和卡常联系在一起的（

$\texttt{Code}$

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib> 
#include <ctime>

inline int min(const int x, const int y) {return x < y ? x : y;}
const int INF = 1e9;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int f[240][1 << 5], c[240][240], rnd[240], n, m, k, ans;
bool mark[240];
std::queue<int> Q;

void spfa(const int S) {
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int k(0); k <= 3; ++ k) {
			int tx(u / m + dx[k]), ty(u % m + dy[k]);
			if (tx < 0 || ty < 0 || n <= tx || m <= ty) continue;
			if (c[tx + 1][ty + 1] == -1) continue;
			int pos(tx * m + ty);
			if (f[u][S] + 1 < f[pos][S]) {
				f[pos][S] = f[u][S] + 1;
				if (!mark[pos]) Q.push(pos), mark[pos] = true;
			}
		}
	}
}

void Steiner() {
	for (int S(1); S < 1 << k; ++ S) {
		for (int i(0); i < n * m; ++ i)
			if (c[i / m + 1][i % m + 1] != -1) {
				for (int S0(S & S - 1); S0; S0 = S0 - 1 & S)
					if (f[i][S] > f[i][S0] + f[i][S ^ S0])
						f[i][S] = f[i][S0] + f[i][S ^ S0] - 1;
				if (f[i][S] < INF) Q.push(i), mark[i] = true;
			}
		spfa(S);
	}
}

void work() {
	memset(f, 0x3f, sizeof f);
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j)
		if (c[i][j] != -1) rnd[c[i][j]] = rand() % k;
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j)
		if (c[i][j] != -1) f[(i - 1) * m + j - 1][1 << rnd[c[i][j]]] = 1;
	Steiner();
	for (int i(0); i < n * m; ++ i) ans = min(ans, f[i][(1 << k) - 1]);
}

int main() {
	srand(time(NULL));
	int T;
	scanf("%d", &T);
	while (T --) {
		ans = INF;
		scanf("%d%d%d", &n, &m, &k);
		for (int i(1); i <= n; ++ i)
		for (int j(1); j <= m; ++ j) scanf("%d", &c[i][j]);
		for (int i(1); i <= 150; ++ i) work();
		printf("%d\n", ans < INF ? ans : -1);
	}
	return 0;
}