Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12497 - Chatgaiya Postman Problem (この記事を編集する[管理者用])

Source

Another Bangladeshi Contest (2012-10-07)
UVa 12497

問題概要

ノード数N (13以下) の無向グラフが与えられる.
問題文の条件1. 2. 3.を満たすパスが何個存在するかを求める問題.
使っている道が全部等しいなら同じとみなす.
条件は簡単に言うと,中心のノードが存在して,中心のノードから長さ3以上のサイクルと移動して中心に帰ってくるというのを2回繰り返し8の字を描くような感じ.
中心のノードはちょうど3回(最初と最後と途中帰ってくる)通って,その他のノードは高々1回のみ訪れる.

解法

中心のノードは全部試し,DPする.
状態は,訪れたノードの集合,何個目のサイクルを移動中か,中心から移動した直後かどうか,今いるノード番号.
O(2^n * n^3).

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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