[THUSCH2017] 巧克力
题目描述
「人生就像一盒巧克力，你永远不知道吃到的下一块是什么味道。」
明明收到了一大块巧克力，里面有若干小块，排成 \(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\%\) 的分数。
先考虑第一问。
当全图只有 \(k\) 种颜色的时候，这是个斯坦纳树问题。考虑把问题向斯坦纳树上靠。
如果我们给每种颜色都映射一个 \([0,k-1]\) 中的数，然后跑斯坦纳树。如果最优答案中的所有颜色被我们映射成了不同的数，我们就能算出答案。
那么概率是多大呢？所有颜色有 \(k!\) 中跑列，而映射成的数有 \(k^k\) 中映射方法。概率是 \(\frac{k!}{k^k}\)，那么期望跑 \(\frac {k^k}{k!}\) 次就能出来。我自己具体是跑了 200 次。
这个斯坦纳树有点特殊的是合并的时候需要减去原来点的代价。
那么考虑第二问，中位数经典做法是二分。 \(n\) 个数的中位数可以表示为最小的 \(k\) 使得大于 \(k\) 的数不超过 \(\lfloor\frac n2\rfloor\) 个，二分 \(k\)，在跑斯坦纳树的时候可以增加一维答案，表示最少答案的情况下最少需要连多少个大于 \(k\) 的数。
本题稍微卡常，可以卡的地方有
- 在随机化时先判定一下最小格子数会不会已经大过目前答案再二分
- 对 \(a_{i,j}\) 离散化后再二分。
- 二分时如果目前的左端点超过目前的中位数最小值就 break
- 斯坦纳树 dp 的时候两维可以压成一个 int
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9,N=230,dx[]={1,0,-1,0},dy[]={0,1,0,-1},B=200;
int T,n,m,k,a[N][N],c[N][N],cl[N],ans,cnt,lsh[N];
pair<int,int>dp[32][N][N];
struct node{
int x,y;
pair<int,int>d;
bool operator<(const node&n)const{
return d>n.d;
}
};
mt19937 gen(10);
pair<int,int>operator+(pair<int,int>u,pair<int,int>v){
return make_pair(u.first+v.first,u.second+v.second);
}
pair<int,int>operator-(pair<int,int>u,pair<int,int>v){
return make_pair(u.first-v.first,u.second-v.second);
}
priority_queue<node>q;
int ok(int x,int y)
{
return c[x][y]!=-1&&x&&y&&x<=n&&y<=m;
}
void dij(int x,int p)
{
while(!q.empty())
{
node k=q.top();
q.pop();
if(k.d!=dp[x][k.x][k.y])
continue;
for(int i=0;i<4;i++)
if(ok(k.x+dx[i],k.y+dy[i]))
if(dp[x][dx[i]+k.x][dy[i]+k.y]>k.d+make_pair(1,a[k.x+dx[i]][k.y+dy[i]]>p))
q.push((node){dx[i]+k.x,dy[i]+k.y,dp[x][dx[i]+k.x][dy[i]+k.y]=k.d+make_pair(1,a[k.x+dx[i]][k.y+dy[i]]>p)});
}
}
pair<int,int>steiner(int x)
{
auto ret=make_pair(INF,INF);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int s=0;s<32;s++)
dp[s][i][j]=make_pair(INF,INF);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(~c[i][j])
dp[1<<cl[c[i][j]]][i][j]=make_pair(1,a[i][j]>x);
for(int s=1;s<(1<<k);s++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int l=s&s-1;l;l=s&l-1)
dp[s][i][j]=min(dp[s][i][j],dp[l][i][j]+dp[s^l][i][j]-make_pair(1,a[i][j]>x));
if(dp[s][i][j].first<=n*m)
q.push((node){i,j,dp[s][i][j]});
}
}
dij(s,x);
if(s==(1<<k)-1)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ret=min(ret,dp[s][i][j]);
}
}
return ret;
}
void slv()
{
int k=steiner(0).first;
if(k>ans)
return;
if(k^ans)
cnt=INF;
ans=k;
int l=0,r=230;
while(l<=r)
{
int md=l+r>>1;
pair<int,int>k=steiner(md);
if(k.second<=ans/2)
r=md-1;
else
l=md+1;
if(l>=cnt)
break;
}
cnt=min(cnt,l);
}
int main()
{
// freopen("chocolate1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
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<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j),lsh[(i-1)*m+j]=a[i][j];
sort(lsh+1,lsh+n*m+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=lower_bound(lsh+1,lsh+n*m+1,a[i][j])-lsh;
ans=cnt=INF;
for(int S=1;S<=B;S++)
{
for(int i=1;i<=n*m;i++)
cl[i]=gen()%k;
slv();
}
if(ans>n*m)
puts("-1 -1");
else
printf("%d %d\n",ans,lsh[cnt]);
}
}