#C241025B. [THUSCH2017] 巧克力
标签（Label）
- 斯坦纳树
- 动态规划
- 状态压缩
- Color Coding
网址（Website）
题目（Problem）
题目描述
「人生就像一盒巧克力，你永远不知道吃到的下一块是什么味道。」
明明收到了一大块巧克力，里面有若干小块，排成 $n$ 行 $m$ 列。每一小块都有自己特别的图案 ，它们有的是海星，有的是贝壳，有的是海螺……其中还有一些因为挤压，已经分辨不出是什么图案了。明明给每一小块巧克力标上了一个美味值 $a_{i,j}$（$0\le a_{i,j}\le 10^6$），这个值越大，表示这一小块巧克力越美味。
正当明明咽了咽口水，准备享用美味时，舟舟神奇地出现了。看到舟舟恳求的目光，明明决定从中选出一些小块与舟舟一同分享。
舟舟希望这些被选出的巧克力是连通的（两块巧克力连通当且仅当他们有公共边），而且这些巧克力要包含至少 $k$（$1\le k\le 5$）种。而那些被挤压过的巧克力则是不能被选中的。
明明想满足舟舟的愿望，但他又有点「抠」，想将美味尽可能多地留给自己。所以明明希望选出的巧克力块数能够尽可能地少。如果在选出的块数最少的前提下，美味值的中位数（我们定义 $n$ 个数的中位数为第 $\left\lfloor\frac{n+1}{2}\right\rfloor$ 小的数）能够达到最小就更好了。
你能帮帮明明吗？
输入格式
每个测试点包含多组测试数据。
输入第一行包含一个正整数 $T$（$1\le T\le 5$），表示测试数据组数。
对于每组测试数据：
输入第一行包含三个正整数 $n,m$ 和 $k$；
接下来 $n$ 行，每行 $m$ 个整数，表示每小块的图案 $c_{i,j}$。若 $c_{i,j}=-1$ 表示这一小块受到过挤压，不能被选中；
接下来 $n$ 行，每行 $m$ 个整数，表示每个小块的美味值 $a_{i,j}$。
输出格式
输出共包括 $T$ 行，每行包含两个整数，用空格隔开，即最少的块数和最小的美味值中位数。
若对于某组测试数据，不存在任意一种合法的选取方案，请在对应行输出两个 $-1$。
样例 #1
样例输入 #1
1
5 4 5
3 4 3 4
5 5 -1 5
-1 4 5 5
5 5 4 2
1 -1 2 4
1 3 1 1
3 2 3 3
4 4 4 5
8 9 9 5
7 2 6 3样例输出 #1
9 5提示
| 测试点编号 | $n,m$ 的限制 | $c_{i,j}$ 的限制 | 部分分说明 |
|---|---|---|---|
| 1 | $n=1,1\le m\le233$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le n\times m$ | $\text{A}$ |
| 2 | $1\le n\times m\le 20$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le n\times m$ | $\text{A}$ |
| 3~4 | $n=2,m=15$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le n\times m$ | $\text{A}$ |
| 5~6 | $1\le n\times m\le 30$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le n\times m$ | $\text{A}$ |
| 7~9 | $1\le n\times m\le 50$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le8$ | $\text{A}$ |
| 10 | $1\le n\times m\le 233$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le8$ | $\text{A}$ |
| 11~12 | $1\le n\times m\le 233$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le8$ | $\text{B}$ |
| 13~15 | $1\le n\times m\le 233$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le14$ | $\text{B}$ |
| 16~20 | $1\le n\times m\le 233$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le n\times m$ | $\text{B}$ |
| 21 | $1\le n\times m\le 233$ | $c_{i,j}=-1$ 或 $1\le c_{i,j}\le n\times m$ | 该测试点不计分。 |
$\text{A}$:若输出的最少块数均正确，但最小中位数存在错误，选手可以获得该测试点 $80%$ 的分数。
$\text{B}$:若输出的最少块数均正确，但最小中位数存在错误，选手可以获得该测试点 $60%$ 的分数。
题解（Solution）
$\qquad$感觉理解的不太清晰。。。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int S = 1<<10;
const int N = 350;
bool ST;
mt19937 rr(time(0));inline int rnd(int l,int r){return rr()%(r-l+1)+l;}
int a[N][N], c[N][N], w[N][N];
int n,m,k;
int f[N][N][S];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
bitset<N> vst[N];
queue<P> q;
void spfa(int s){
while(q.size()){
int x,y;tie(x,y)=q.front();q.pop();
vst[x][y] = false;
For(k,0,3){
int i = x+dx[k], j = y+dy[k];
if(in(i,1,n) && in(j,1,m) && ~c[i][j]){
if(f[x][y][s] + w[i][j] < f[i][j][s]){
f[i][j][s] = f[x][y][s] + w[i][j];
if(!vst[i][j])q.push({i,j}),vst[i][j]=true;
}
}
}
}
}
int COL[N*10],to[N],tot;
auto col=COL+114514;
int calc(){
int res = inf;
For(_,1,200){
// shuffle(col + 1, col + tot + 1, rr);
For(i, 1, tot) to[col[i]] = rnd(0,k-1);
For(i,1,n) For(j,1,m){
For(s, 0, (1 << k) - 1) f[i][j][s] = inf;
if(c[i][j]!=-1) f[i][j][1<<to[c[i][j]]] = w[i][j];
}
For(s,1,(1<<k)-1){
For(i,1,n) For(j,1,m) if(~c[i][j]){
for(int t = s & (s-1); 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] <= inf) q.push({i,j}),vst[i][j]=true;
}spfa(s);
}For(i,1,n) For(j,1,m) res = min(res, f[i][j][(1<<k)-1]);
}return res;
}
void Solve(){
n = rd(), m = rd(), k = rd();
For(i,1,n) For(j,1,m) c[i][j] = col[++tot] = rd();
For(i,1,n) For(j,1,m) a[i][j] = rd(), w[i][j] = 1;
sort(col+1,col+tot+1),tot = unique(col+1,col+tot+1)-col-1;
int res = calc();
if(res == inf) return printf("-1 -1\n"),void();
int l = 0, r = 1e6, mid;
while(l<r){
mid = (l+r)>>1;
For(i,1,n) For(j,1,m) w[i][j] = a[i][j]<=mid ? 9999 : 10001;
int now = calc();
if(now <= res * 10000) r = mid;
else l = mid+1;
}printf("%d %d\n", res, l);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
int T = rd();double Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
