Problem 1040 : Chocolate with Heart Marks
問題概要
日本語の問題なので本文参照(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1040)
1x1の小正方形からなるh*wの長方形がある。
この長方形のなかにはいくつかハートマークのある板がある。
ハートマークのある板をつなげたまま食べられるチョコレートの枚数の最大値を求めよ。
解法
チョコレートの格子をグラフにする。
(隣接する板にコスト1の枝を張る。)
このグラフの、ハートのノードを全て含むような最小シュタイナー木を求めれば、それが残るチョコレートの枚数-1になるため、全体の枚数から引き算すればよい。
最小シュタイナー木のライブラリはm[i][i]=0としないと上手く動かない模様。
ソースコード
spaghetti source最小シュタイナー木のコードを使用。
int dy[]={-1,0,1,0},dx[]={0,-1,0,1}; int h,w; int main() { while(scanf("%d%d",&h,&w),h){ Matrix m(h*w,Array(h*w,inf)); vi heart; rep(i,h)rep(j,w){ int t; scanf("%d",&t); if(t)heart.pb(i*w+j); rep(d,4){ int ny=i+dy[d],nx=j+dx[d]; if(ny<0||ny>=h||nx<0||nx>=w)continue; m[ny*w+nx][i*w+j]=m[i*w+j][ny*w+nx]=1; } m[i*w+j][i*w+j]=0; } int ans=minimum_steiner_tree(heart,m); printf("%d\n",h*w-ans-1); } return 0; }