解题报告

题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,j$ 这个点与 $s$ 这些颜色连通的最优解，最后枚举大小为 $K$ 的集合更新答案。

然而……颜色数有250种，根本不可能存下状态，但是 $K$ 却非常小，于是可以乱搞：

随机把每种颜色映射到 $[1,K]$ 中，然后做斯坦纳树，这样复杂度就正常了。

考虑答案正确的概率，假设最优解选取的颜色集合为 $C$ ，则 $C$ 中的 $K$ 个点不能重复，也就是一个 $K$ 的排列，所以概率为 ${K!\over K^K}\approx0.006119899$ ，那么随机个 $400$ 次，概率就变成 $90\%$ 了，如果你的代码常数小，可以考虑随机 $800$ 次，这样概率就变成 $99\%$ 了。

其实还可以映射到 $[1,K+c]$（ $c$ 是个小常数），这样正确概率会大一些，但是时间复杂度也会多个常数。

示例程序

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

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

inline bool Fmin(int &x,int y) {return y<x?(x=y,true):false;}
#define AM(x) ((x)<maxt?(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;
        }
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    srand(759405);scanf("%d%d%d",&n,&m,&K);int X,Y;
    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",&p[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (c[i][j]>0) C[++C[0]]=c[i][j];
    sort(C+1,C+1+C[0]);C[0]=unique(C+1,C+1+C[0])-C-1;ans=2e9;
    for (int t=1;t<=400;t++){
        random_shuffle(C+1,C+1+C[0]);for (int i=1;i<=C[0];i++) ha[C[i]]=i%K;
        memset(f,63,sizeof(f));INF=f[0][0][0];
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) c[i][j]>0?f[i][j][1<<ha[c[i][j]]]=p[i][j]:0;
        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]);
    }ans==INF?puts("-1"):printf("%d\n",ans);return 0;
}