Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2395-9c9859f4
この記事にトラックバックする(FC2ブログユーザー)

UVa 12549 - Sentry Robots (この記事を編集する[管理者用])

Source

An European Reginal contest to be decided, SWERC 2012 Online (2012-11-24)
UVa 12549

問題概要

100*100以下のグリッドが与えられる.
グリッドには障害物と,監視したい点がある.
障害物は視界を遮る.
監視カメラを置くと,おいたセルを含めて,そのセルから上下左右の一方向に幅1の半直線上のセルをすべて監視できる.(障害物にあたったらそこまで)
すべての監視したい点を監視するために置かなければいけない監視カメラの数を求める問題.

解法

最大流.
縦,横の各線分を切り出して,それぞれを二部グラフの左右に置く.
各監視したい点について,それが属す縦横セグメント達の間に枝を貼る.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2395-9c9859f4
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。