Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

PKU 3764 - The xor-longest Path (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3764

問題概要

枝に重みがつけられた,ノード数100000以下の全域木が与えられる.
パスの重みは,そのパスに含まれる全ての枝のXORで定める.
重み最大のパスの重みを求める問題.

解法

まず適当な始点を決めてあげて,その始点から全てのノードまでの(XORで定義された)距離d[i]を求める.
ノードaとノードb間の距離はd[a] XOR d[b]で計算可能.
なので,d[i]から2つ選んで,XOR取って最大となる組み合わせを探せば良い.
2分探索っぽく,上位ビットから決めていく.
上位ビットのみ考えて,それが達成できるかどうか,相方が存在するかどうかをhashなどを使って探索する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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