Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 3271 - The Traveling Judges Problem (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3271

問題概要

意訳して問題概要を書く.
ノード数20以下の無向グラフが与えられる.
その中でノードのサブセットが1個与えられる.
そのノードのサブセットを含むノードのセットの最小全域木の中で,コスト最小のものを求める問題.
ただし,複数あるなら,ノード数が最小のもの,それでも複数あるなら,使うノードの種類が辞書順最小のものを求める.

解法

ノードを使うかどうか,たかだか2^20程度(実際には2^18まで)なので,全部最小全域木作って調べる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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