自动搬运

查看原文

来自洛谷，原作者为

	LPF 看不懂黑白却听得到钟摆，去新世界冒险和内心作伴

搬运于2025-08-24 22:29:59，当前版本为作者最后更新于2022-02-04 21:07:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{A Solution with Code}$

巧克力

给定 $n\times m$ 的网格以及两个参数 $a,c$。

要求选出一个连通块，不包含 $c=-1$ 的网格，且 $c$ 的种类数 $\geq k$。

在此前提下最小化连通块大小，并在此前提下最小化 $a$ 的中位数。

中位数直接套路的二分解决，不是本题的重点。看到 $k\leq 5$ 很难不想到一些偏乱搞的做法。

当 $n\times m$ 较小时，可以直接 $\binom{n\times m}{k}$ 钦定关键点，跑最小斯坦纳树的模板。

对更大的情况，考虑随机化，将所有颜色任意映射至 $[0,k)$ 中。

当最优解包含的 $k$ 个点被分配到不同的颜色中即可正确，一次成功的概率大概是 $P=k!/k^k$。

由于 $(1-P)^{200}$ 早已 $<1\%$，故正确性也基本上没啥问题。

实现上，这里的斯坦纳树将所有同色节点都近似的缩成了一个点，故初始化的时候有些特殊。

时间复杂度大概是 $O(Tnm3^k\log V)$。

#include<bits/stdc++.h>
typedef long long LL;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

const int N = 300;
const int INF = 0x3f3f3f3f;
int n, m, k, c[N][N], a[N][N], w[N][N], tt, col[N], to[N];
int f[N][N][1 << 6]; bool vis[N][N];
mt19937 myrand(20060814);

#define MP make_pair
typedef pair<int, int> PII;
queue<PII> q;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

void spfa(int s) {
	while(! q.empty()) {
		PII now = q.front(); q.pop();
		int x = now.first, y = now.second;
		vis[x][y] = false;
		rep(o, 0, 3) {
			int tx = x + dx[o], ty = y + dy[o];
			if(tx < 1 || tx > n || ty < 1 || ty > m || c[tx][ty] == - 1) continue;
			if(f[x][y][s] + w[tx][ty] < f[tx][ty][s]) {
				f[tx][ty][s] = f[x][y][s] + w[tx][ty];
				if(! vis[tx][ty]) q.push(MP(tx, ty)), vis[tx][ty] = true;
			}
		}
	}
}

int work() {
	int ans = INF;
	rep(Q, 1, 233) {
		shuffle(col + 1, col + tt + 1, myrand);
		rep(i, 1, tt) to[col[i]] = i % k;
		rep(i, 1, n) rep(j, 1, m) {
			rep(s, 0, (1 << k) - 1) f[i][j][s] = INF;
			if(~ c[i][j]) f[i][j][1 << to[c[i][j]]] = w[i][j];
		}
		rep(s, 1, (1 << k) - 1) {
			rep(i, 1, n) rep(j, 1, m) if(~ c[i][j]) {
				for(int t = (s - 1) & s; t; t = (t - 1) & s)
					f[i][j][s] = min(f[i][j][s], f[i][j][t] + f[i][j][s ^ t] - w[i][j]);
				if(f[i][j][s] < 1e9) q.push(MP(i, j)), vis[i][j] = true;
			}
			spfa(s);
		}
		rep(i, 1, n) rep(j, 1, m) ans = min(ans, f[i][j][(1 << k) - 1]);
	}
	return ans;
}

int main() {
	int T = read();
	while(T --) {
		tt = 0;
		n = read(), m = read(), k = read();
		rep(i, 1, n) rep(j, 1, m) c[i][j] = col[++ tt] = read();
		rep(i, 1, n) rep(j, 1, m) a[i][j] = read(), w[i][j] = 1;
		sort(col + 1, col + tt + 1);
		tt = unique(col + 1, col + tt + 1) - (col + 1);

		int rec = work();
		if(rec == INF) {puts("-1 -1"); continue;}
		int l = 0, r = 1e6;
		while(l < r) {
			int mid = (l + r) >> 1;
			rep(i, 1, n) rep(j, 1, m) w[i][j] = ((a[i][j] <= mid) ? 9999 : 10001);
			int now = work();
			if(now <= rec * 10000) r = mid; else l = mid + 1;
		}
		printf("%d %d\n", rec, l);
	}
	return 0;
}