Codechef 12.4 CONNECT 随机化+斯坦纳树
题目大意：
给定一个$n\times{m}$的矩阵，其中每个位置都有一个数，数的范围是$[-1,n\times{m}]$，每个位置还有一个选择这个位置需要付出的代价，每个代价都为正数。
现在要求选择矩阵中的若干个位置组成一个四连通的连通块，使得其中至少有$k$种不同的正数，同时最小化付出的总代价。
数据范围$n,m\leq{15},k\leq{7}$。
算法讨论：
如果数值的范围为$[-1,k]$之间，那么就很好做了，直接利用斯坦纳树模型就可以了。
我们考虑随机将$[1,n\times{m}]$区间中的数映射到$[1,k]$中，然后这样做一次，能得到正确答案的概率为$\frac{k!}{k^k}$，那么我们随机做$T$次，当$T=300$的时候就能够通过Tsinsen上的数据了。
时空复杂度：
时间复杂度$O(T(3^k+2^k\times{SPFA(n\times{m},n\times{m})}))$，空间复杂度$O(nm2^k)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 0x1f1f1f1f
#define N 16
#define M 16
#define K 7
int n, m, k, a[N][M], w[N][M], ch[N * M];
int f[N][M][1 << K];
queue<pair<int, int> > q;
bool vis[N][M];
static const int dx[] = {-1, 0, 0, 1};
static const int dy[] = {0, -1, 1, 0};
#define inrange(x, l, r) ((x) >= (l) && (x) <= (r))
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
srand(19980302);
cin >> n >> m >> k;
int i, j;
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
scanf("%d", &w[i][j]);
int T = 300, s, _s, x, y, ans = inf;
while (T--) {
for (i = 1; i <= n * m; ++i)
ch[i] = rand() % k;
//ch[0] = k;
memset(f, 0x1f, sizeof f);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
if (a[i][j] == 0)
f[i][j][0] = w[i][j];
else if (a[i][j] != -1)
f[i][j][1 << (ch[a[i][j]])] = w[i][j];
for (s = 1; s < (1 << k); ++s) {
for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j) {
if (a[i][j] != -1) {
for (_s = (s - 1) & s; ; (--_s) &= s) {
f[i][j][s] = min(f[i][j][s], f[i][j][_s] + f[i][j][s ^ _s] - w[i][j]);
if (_s == 0)
break;
}
if (f[i][j][s] != inf) {
vis[i][j] = 1;
q.push(make_pair(i, j));
}
}
}
}
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
vis[x][y] = 0;
for (i = 0; i < 4; ++i)
if (inrange(x + dx[i], 1, n) && inrange(y + dy[i], 1, m))
if (a[x + dx[i]][y + dy[i]] != -1 && f[x + dx[i]][y + dy[i]][s] > f[x][y][s] + w[x + dx[i]][y + dy[i]]) {
f[x + dx[i]][y + dy[i]][s] = f[x][y][s] + w[x + dx[i]][y + dy[i]];
if (!vis[x + dx[i]][y + dy[i]]) {
vis[x + dx[i]][y + dy[i]] = 1;
q.push(make_pair(x + dx[i], y + dy[i]));
}
}
}
}
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
ans = min(ans, f[i][j][(1 << k) - 1]);
//printf("%d\n", ans);
}
printf("%d\n", ans == inf ? -1 : ans);
return 0;
}
评论 (0)