P7450 [THUSCH2017] 巧克力

· · 题解

\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;
}