Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11706 - Party Night (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11706

問題概要

街人100人以下の人がいて,それぞれ会ったことがあるかどうかが与えられる.
ある2人が会ったことがあるという関係は1000個以下.
この街では2回パーティーを行い,それぞれのパーティーは複数の会場で行われた.
同じ会場にいた人は全部会ったことがあるという関係が成り立つ.
また,同じ2人が,2回とも同じ会場にはいなかった.
矛盾がないかどうかを調べる問題.

解法

街人をノード,会ったことがある関係を枝と書く.
それぞれ枝の色を塗る.それは1回目のパーティーで知り合ったか,2回目のパーティーで知り合ったかの2色.
 3ノード間に3つの枝があれば,全て同じ色でぬらなくてはいけない.
 3ノード間に2つの枝があれば,違う色でぬらなくてはいけない.
という条件から,2彩色可能かどうかという問題に落ちる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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