Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12017 - Imitation (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12017

問題概要

有向グラフが与えられる.
そのグラフにおいて,ノードaからノードbに移動できる,という性質を全て保ったまま枝を追加したり削除したりできる.
最終的なグラフの枝数の最小値と最大値を求める問題.
ノード数は1000以下,枝数は10000以下.

解法

まず,強連結成分分解する.
連結成分の中は,
 最小値:ノード数が1なら何もしない,そうでなければノード数だけ枝を使って閉路を作る
 最大値:完全グラフにする
とすれば良い.
後は,DPして,その連結成分から辿りつける連結成分を求めて,最小になるように,最大になるように枝をはれば良い.
愚直にやるとO(N^3)になるので,色々工夫したけどやっぱり最悪だとO(N^3)になりそうなコードで通った.
あんまり工夫しなくてもいけたのかも?

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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