Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 2168 - Luigi's Tavern (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 2009 夏合宿 3日目
Aizu 2168

問題概要

勇者と戦士と僧侶と魔法使いがそれぞれ50人以下いる.
同じパーティー内の勇者と戦士,戦士と僧侶,僧侶と魔法使いはそれぞれ仲が良くないとダメ.
僧侶がいないパーティーは戦士と魔法使いはいなければいけない.
全てのパーティーに勇者はいなくてはいけない.
戦士のいないパーティー,僧侶のいないパーティー,魔法使いのいないパーティーはそれぞれ,N_W, N_C, N_M以下でなければならない.
仲が良い人のリストが与えられたとき,最大で何個のパーティーが作れるか求める問題.

解法

まず,N_W人の戦士などを追加して考える.
追加した人は全て仲が良いが,追加した僧侶は,追加した戦士,魔法使いと仲が悪いとすれば良い.
後は,
 (ソース) - 勇者 - 戦士 - 僧侶 - 魔法使い - (シンク)
といったグラフを作って最大流を流せば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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