きままにものづくりスマートフォン用の表示で見るきままにものづくり日々の気付いたことなんかを書いてます。この広告は、90日以上更新していないブログに表示しています。2014-12-12SRM625Div1Medium問題サイズNの平面を考える。スタート点'b'と穴'H'とゴール'$'と通常のパネル'.'が存在する。'b'は複数存在し、その上には駒が置いてある。駒は上下左右に3マスずつ移動可能である。駒の移動先、もしくは移動する間の2つのマスが'H'ならそのマスへは移動できない。駒を'H'に到達させないようにするために必要な最小の'H'の追加数を求めよ。解法この問題は最小カット問題へと帰着できる。スタート点が複数あるが、sourceとsinkを別に作り無限のcapacityを持つエッジで結ぶことで解くことができる。答えである流量Fは最大でも8である。エッジの数は頂点の数の2上に比例する。頂点の数はN/3となる。(1)月別アーカイブはてなブログをはじめよう!even_ekoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。