Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12519 - The Farnsworth Parabox (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12519

問題概要

ノード数100以下の有向グラフを考える.
枝が与えられるが,(u, v)の枝がコストxと与えられた場合,vからuへはコスト-xで移動できる.
コストの和が0でない閉路が存在するかどうかを判定する問題.

解法

コストが正の閉路が存在するなら,逆にたどればコストが負の閉路も存在するので,負の閉路が存在するかどうかを調べれば良い.
ワーシャルフロイドして対角成分が負になるものがでてくるかどうかを調べた.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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