LYK loves graph(Auribus Oculi Fideliores Sunt)

题目描述
LYK 有一个 $n\ast m$ 的网格图，每个格子都填有$-1$ 至 $n\ast m-1$ 中的其中一个数表示它的颜色
且每个格子都有一个代价 a i , j a_{i,j} ai,j​。
它想选择一个四联通块，使得该四联通块中，存在至少 $k$ 种不同的颜色，且不包含$-1$，
要使得所选的格子的代价和最小。
输入格式
第一行三个整数，$n,m,k$.
接下来 $n$ 行，每行 $m$ 个数，表示矩阵每个位置的颜色，每个数在$-1$ 到 $n\ast m-1$ 之间。
接下来 n 行，每行 m 个数，表示选择该位置所需要的代价
1 < = n , m < = 15 ， 1 < = k < = 7 ， 1 < = a i , j < = 100000 。 1<=n,m<=15，1<=k<=7，1<=a_{i,j}<=100000。 1<=n,m<=15，1<=k<=7，1<=ai,j​<=100000。

百闻不如一见。
首先颜色数$<=10$的时候就是斯坦纳树裸题。

结束了。

$\mathrm{A}\mathrm{C}\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
using namespace std;int n,m,K,col[20][20],a[20][20],buf[20][20];
int f[16][16][1<<7],bit[1<<7];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
#define pii pair
#define pb push_back
#define mp make_pairint mAp[300];int main(){freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);scanf("%d%d%d",&n,&m,&K);rep(i,1,n) rep(j,1,m) scanf("%d",&buf[i][j]);rep(i,1,n) rep(j,1,m) scanf("%d",&a[i][j]);int ans = 0x3f3f3f3f;for(int stp=300;stp--;){memset(f,0x3f,sizeof f);rep(i,0,n*m-1) mAp[i] = rand() % K; rep(i,1,n) rep(j,1,m) if(buf[i][j] >=0) col[i][j] = mAp[buf[i][j]];else col[i][j] = -1;rep(i,1,n) rep(j,1,m) (col[i][j] >=0) && (f[i][j][1<<col[i][j]] = a[i][j]);rep(i,1,(1<<K)-1) bit[i] = bit[i>>1] + (i&1);rep(sta,1,(1<<K)-1){static queue<pair<int,int> >q;bool inq[20][20]={};for(int s=(sta-1)&sta;s;s=(s-1)&sta)rep(i,1,n) rep(j,1,m) if(col[i][j] >= 0)f[i][j][sta] = min(f[i][j][sta],f[i][j][s]+f[i][j][sta^s]-a[i][j]);rep(i,1,n) rep(j,1,m) if(f[i][j][sta] < 0x3f3f3f3f)q.push(mp(i,j));for(int x,y,u,v;!q.empty();){x = q.front().first , y = q.front().second , q.pop();rep(i,0,3) if((u=x+dir[i][0])>=1 && u<=n && (v=y+dir[i][1])>=1 && v<=m && col[u][v] >= 0 && f[u][v][sta] > f[x][y][sta] + a[u][v])f[u][v][sta] = f[x][y][sta] + a[u][v],(!inq[u][v]) && (inq[u][v]=1,q.push(mp(u,v)),0);inq[x][y] = 0;}}rep(sta,1,(1<<K)-1) if(bit[sta] == K) rep(i,1,n) rep(j,1,m) ans = min(ans , f[i][j][sta]);}printf("%d\n",ans);}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！