题目概述

给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中位数也要最小。

解题报告

人类智慧题QAQ，首先第一问和这道题是一样的，用随机+斯坦纳树就可以解决。

但是第二问是什么鬼？首先我们可以二分中位数，然后就可以把美味值分成两种，大于中位数和小于等于中位数。由于先要满足个数最小，所以我们可以这样……将小于等于中位数的值设为 $9999$ ，大于中位数的设为 $10001$ ……

因为 $K$ 个不同形状连通，至多需要选 $5(233+233)\approx2500$ 个（肯定比这个值小），只要把新的权值设置的比 $2500$ 大，权值最小就等价于个数最少了！ 而且这样我们还可以通过权值 $ans$ 来求出个数 $\lfloor{ans+2500\over10000}\rfloor$ ，从而进行二分验证：满足的条件是小于等于中位数的个数大于等于大于中位数的个数，即 $ans\le 10000\lfloor{ans+2500\over10000}\rfloor$ 。

示例程序

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=233,maxk=5,maxc=maxn*maxn,maxs=1<<maxk,INF=1061109567;
const int dif[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

int te,n,m,K,c[maxn+5][maxn+5],a[maxn+5][maxn+5],p[maxn+5][maxn+5],C[maxc+5],ha[maxc+5];
int f[maxn+5][maxn+5][maxs];pair<int,int> que[maxc+5];
int Head,Tail;bool vis[maxn+5][maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline bool Fmin(int &x,int y) {return y<x?(x=y,true):false;}
#define AM(x) ((x)<maxc?(x)+1:0)
inline void Spfa(int s){
    while (Head!=Tail){
        pair<int,int> now=que[Head=AM(Head)];int x=now.fr,y=now.sc;vis[x][y]=false;
        for (int t=0;t<4;t++){
            int xx=x+dif[t][0],yy=y+dif[t][1];if (xx<1||xx>n||yy<1||yy>m||c[xx][yy]<0) continue;
            if (Fmin(f[xx][yy][s],f[x][y][s]+p[xx][yy])&&!vis[xx][yy])
                que[Tail=AM(Tail)]=mp(xx,yy),vis[xx][yy]=true;
        }
    }
}
inline int DP(int mid,int ans=INF){
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) p[i][j]=(a[i][j]<=mid?9999:10001);
    for (int t=1;t<=150;t++){
        random_shuffle(C+1,C+1+C[0]);for (int i=1;i<=C[0];i++) ha[C[i]]=i%K;
        for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) for (int s=0;s<(1<<K);s++) f[i][j][s]=INF;
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (~c[i][j]) f[i][j][1<<ha[c[i][j]]]=p[i][j];
        for (int s=1;s<(1<<K);Spfa(s++),Head=Tail=0)
            for (int i=1;i<=n;i++)
                for (int j=1;j<=m;j++){
                    for (int t=(s-1)&s;t;t=(t-1)&s) Fmin(f[i][j][s],f[i][j][t]+f[i][j][s^t]-p[i][j]);
                    if (f[i][j][s]<INF) que[Tail=AM(Tail)]=mp(i,j),vis[i][j]=true;
                }
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) ans=min(ans,f[i][j][(1<<K)-1]);
    }return ans;
}
inline int Solve(int L,int R){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
        int ans=DP(mid);if (ans==INF) return -1;
        ans<=(ans+2500)/10000*10000?R=mid-1:L=mid+1;
    }return L;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (srand(759405),readi(te);te;te--){
        readi(n);readi(m);readi(K);
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) readi(c[i][j]);
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) readi(a[i][j]);
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (~c[i][j]) C[++C[0]]=c[i][j];
        sort(C+1,C+1+C[0]);C[0]=unique(C+1,C+1+C[0])-C-1;int B=Solve(0,1e6),A=DP(B);
        A<INF?printf("%d %d\n",(A+2500)/10000,B):puts("-1 -1");
    }return 0;
}