Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Aizu 2096 - Private Teacher (この記事を編集する[管理者用])

Source

ICPC OB/OG会 夏合宿2007: 3日目
Aizu 2096

問題概要

家庭教師をしていて,1日に1人まで教える.テストまで残りw週だけ残されている.
生徒は100人以下いて,それぞれ,教えてもらいたい回数と,暇な曜日が与えられる.
上手くスケジュールを組むことで,全員の教えてもらいたい回数を満たすことができるかどうかを判定する問題.
wは10^10以下.

解法

最大流.グラフの概形は
 ソース -(流量はw)- 曜日 -(流量は無限大)- 生徒 -(流量は教えてもらいたい回数)- シンク
64bit整数を使わないと駄目なことに注意.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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