Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12430 - Grand Wedding (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12430

問題概要

無向グラフが与えられる.枝には長さが設定されている.(ノード数,枝数の制限は書いていない)
各ノードには,守備兵を置くか置かないか,のどちらかにしたいが以下の条件を満たすようにしたい.
 全ての枝のちょうど一方の端にのみ守備兵がいる
条件をみたすことができるかどうかを判定する問題.
もし条件をみたすことが出来なければ,以下のことをして良い.
 長さK以上の枝をすべて破壊する(ただし,全ての枝を破壊してはいけない)
これで条件をみたすことができるならば,そのような最大のKを求める問題.

解法

守備兵が置けるかどうかは,2彩色可能かどうかなので,判定自体は簡単.
2分探索すれば良い.(らしい)
判定する方法として,各ノードkを2倍してノードk+とノードk-にして,(それぞれ守備兵を置く,置かないに相当)
ノードiとノードjに枝があるなら,
 ノードi+とノードj-を繋げ (iに守備兵を置くなら,jには置かないという意味)
 ノードi-とノードj+を繋げ
ノードk+とノードk-が連結でなければ2彩色可能.(連結なら,kに守備兵を置くなら,kに守備兵を置かないという意味になって矛盾)
なので,枝を長さでソートして,短い方からunion findしても良い.(自分はこっちでやった)

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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