Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12533 - Joining Couples (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12533

問題概要

Nノードの有向グラフを考える.(Nは10^5以下)
各ノードからはちょうど1つの枝が出ている.
Q個 (10^5) のクエリに答える問題.
各クエリは,ノードA, Bが与えられる.
各ターン,A, Bのどちらかが,枝にそって1個移動できる.
ノードが一致するまでの最小ターン数を求める.一致させられないならそれを指摘する.

解法

移動していくと,いずれループに陥る.ループは連結成分ごとに1つだけ(枝数の関係より).
そのため,同じ連結成分であれば必ず一致できる.
どのノードがループの一員かを調べておいて,ループ内のノードは順番に番号をつけておく.
ループのサイズと,ループ内のノードの番号から,ループの中では最小ターンがO(1)で求められる.
ループをルートとする木を考えて,ループに辿り着くまでの枝数と,ループに辿り着くノードの番号を計算する.
後は,LCAをdoubling等でO(log N)やO(1)求められるようにしておく.
すると,お互いLCAに移動するのが最小ターン数になる(距離はループに辿り着くまでの枝数から計算できる)し,
LCAがルートの場合,ループ内での最小距離も使えば求まる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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