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;
}