simezi_tan https://blog.hatena.ne.jp/simezi_tan/ simezi_tanの日記 https://simezi-tan.hatenadiary.org/ AOJ グラフ理論 問題概要 日本語の問題なので本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1040）1x1の小正方形からなるh*wの長方形がある。 この長方形のなかにはいくつかハートマークのある板がある。 ハートマークのある板をつなげたまま食べられるチョコレートの枚数の最大値を求めよ。 解法 チョコレートの格子をグラフにする。 （隣接する板にコスト１の枝を張る。） このグラフの、ハートのノードを全て含むような最小シュタイナー木を求めれば、それが残るチョコレートの枚数-1になるため、全体の枚数から引き算すればよい。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsimezi-tan.hatenadiary.org%2Fentry%2F20101006%2F1286350878" title="Problem 1040 : Chocolate with Heart Marks - simezi_tanの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-10-06 16:41:18 rich https://simezi-tan.hatenadiary.org/entry/20101006/1286350878 1.0 100%