Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12437 - Kisu Pari Na 2 (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12437

問題概要

ノード数N,枝数Mの無向グラフが与えられる.(Nは10000以下,グラフはループがない,つまり森)
枝を1回移動するたびにコストが1だけかかる.
10000個以下のクエリが与えられる.
各クエリでは,1つの正整数Kが与えられるので,異なるK個のノードを訪れるための最小コストを求める.
最初はどこにいても良いし,最初にいるノードは訪れたとみなして良い.

解法

各森について,ノード間の距離の最大値を求めておく.
その最大値以下なら,いったり戻ったりせずに移動できる.
そうでなければ,その最長パスにそって,途中で寄り道しながら移動したと思えば,最大値を超えた分は1ノードあたりコスト2かかる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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