1040 Chocolate with Heart Marks

グラフな難問．しゅたいなー木．

1040

グラフで，あるノードの部分集合が与えられた時，その部分集合に含まれるノード全てをつなぐ木を「シュタイナー木」というらしい．全ての頂点を含む時は全域木．
そして，シュタイナー木のうち重みが最小な木を見つける問題が「最小シュタイナー木問題」．
もともとはユークリッド距離の場合とマンハッタン距離の場合がある．
パソコンをネットワークでつなぐのに使うLANケーブルの長さを最小にするネットワーク配線問題とか．

この問題はマンハッタン距離での場合で，SpaghettiSourceさん( http://www.prefield.com/algorithm/dp/steiner_tree.html )をそのまま借りた．

重みが1の格子上のグラフで，最小シュタイナー木を求めて，その木の重み+1が残すべきチョコレートのブロック数．全ブロック数からこのブロック数を引いたものが答え．

無理すぎる．