Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11733 - Airports (この記事を編集する[管理者用])

Source

A Bangladeshi Contest (2009-12-19) (blog)
UVa 11733

問題概要

n個の都市と,各都市間を結ぶ道を作るのに必要なコストが与えられる.
各都市に空港を作るコストも与えられる.
全ての都市から空港に移動できるようにするために,必要なコストと空港の数を求める問題.
必要なコストが等しいなら,空港の数は大きい方が良い.
nは10000以下,作れる道の数は100000以下.

解法

作った道のコスト+連結成分の数 * 空港建設コストだけかかるので,見ている枝のコストが空港のコストより小さい間,クラスカルすれば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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