Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4449 - Fare and Balanced (この記事を編集する[管理者用])

Source

ACM/ICPC World Finals - Stockholm - 2008/2009
LiveArchive 4449

問題概要

ノード数50000以下,枝数50000以下のDAG (閉路のない有向グラフ)が与えられる.ノード数をNとする.
ノード1からノードNに移動する全てのパスを考えて,全てのパスが同じ距離になるように,幾つかの枝に重みを付け加えたい.
ただし,全てのパスは,重みを付け加えたパスが2個以上含まれてはいけない.
そのように重みの付け加え方を1つ求める問題.
複数あるなら,ノード1からノードNに移動する距離を最小にする.それでも複数あるならどれでも良い.
全てのノードは,ノード1からノードNに移動するどれかのパスに含まれる.

解法

ノード1からノードkまでの最小距離と最大距離,ノードkからノードNまでの最小距離と最大距離をDPで計算する.
全てのノードkに対して,どちらかは,最小距離と最大距離が一致してないと達成できない.
後は,全ての枝(a,b)に対して,ノード1からノードaまでの最小距離と最大距離が同じで,ノードbからノードNまでの最小距離と最大距離が同じ場合に重みを付け加える.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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