考虑颜色比较少的时候,第一问可以直接斯坦纳树
第二问考虑二分,每次把每格的权值给成1000+[a[i]>m],就是在个数最少的基础上尽量选小于等于m的
然而颜色太多不能直接做,但可以把每种颜色映射到5以内,这样的话,做一次的正确率就是作为答案的那5种颜色分别被映射到了1~5的概率,就是$\frac{5!}{5^5}=0.0384$,做233次正确率就有$99.989\%$了
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pa;
const int maxn=,maxp=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int step[][]={{,},{,-},{,},{-,}};
int id[maxn][maxn],pct,pos[maxn][];
int N,M,S,K;
int f[maxn][maxp],c[maxn],a[maxn],val[maxn];
int hsh[maxn],C; queue<int> q;
bool flag[maxn];
inline void spfa(int s){
for(int i=;i<=pct;i++) if(c[i]!=-) flag[i]=,q.push(i); while(!q.empty()){
int p=q.front();q.pop();
flag[p]=;
int x=pos[p][],y=pos[p][];
for(int j=;j<;j++){
int nx=x+step[j][],ny=y+step[j][];
if(nx<||ny<||nx>N||ny>M||c[id[nx][ny]]==-) continue;
int ni=id[nx][ny];
if(f[ni][s]>f[p][s]+val[ni]){
f[ni][s]=f[p][s]+val[ni];
if(!flag[ni]) q.push(ni),flag[ni]=;
}
}
}
} inline int solve(){
CLR(f,);
for(int i=;i<=pct;i++) if(c[i]!=-) f[i][<<hsh[c[i]]]=val[i];
for(int s=;s<(<<K);s++){
for(int i=;i<=pct;i++){
if(c[i]==-) continue;
for(int ss=(s-)&s;ss;ss=(ss-)&s){
f[i][s]=min(f[i][s],f[i][ss]+f[i][s^ss]-val[i]);
}
}
spfa(s);
}
int ans=1e9;
for(int i=;i<=pct;i++) ans=min(ans,f[i][(<<K)-]);
return ans;
} int main(){
//freopen("","r",stdin);
srand();
for(int T=rd();T;T--){
pct=,C=;
N=rd(),M=rd(),K=rd();
for(int i=;i<=N;i++){
for(int j=;j<=M;j++) id[i][j]=++pct,pos[pct][]=i,pos[pct][]=j;
}
for(int i=;i<=N;i++) for(int j=;j<=M;j++) c[id[i][j]]=rd(),C=max(C,c[id[i][j]]);
for(int i=;i<=N;i++) for(int j=;j<=M;j++) a[id[i][j]]=rd();
int ans1=1e9,ans2=1e9;
for(int t=;t<=;t++){
for(int i=;i<=C;i++) hsh[i]=rand()%K;
int l=,r=1e6,a1=1e9,a2=1e9;
while(l<=r){
int m=(l+r)>>;
for(int i=;i<=pct;i++) val[i]=(c[i]==-?1e8:+(a[i]>m));
int re=solve();
if(re>=1e8) break;
a1=re/;
int x=a1-(re-a1*);
if(x>=(a1+)/) a2=m,r=m-;
else l=m+;
}
if(a1<ans1||(ans1==a1&&a2<=ans2)) ans1=a1,ans2=a2;
} printf("%d %d\n",ans1==1e9?-:ans1,ans1==1e9?-:ans2);
}
return ;
}