Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 2249 - Road Construction (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬アジア地区予選2010 (2010-11-28) (関西オンサイト参加記録)
Aizu 2249

問題概要

ノード数10000以下,枝数20000以下の有向グラフが与えられる.
枝には距離とコストが設定されていて,ノード0から他の任意のノードまで行くパスがある.
ノード0から他の任意のノードまで行く最小距離を保ったまま枝を減らしたい.
最終的なグラフの枝のコストの和の最小値を求める問題.

解法

ダイクストラして使える枝を列挙して,DAGに落とし,自分に入ってくる枝のうちコストが最小のものを採用する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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