Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12679 - It Can Be Arranged (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12679

問題概要

$N$ 個の授業があり,授業 $k$ の開始時間 $A_k$ と終了時間 $B_k$,その授業の受講者 $S_k$ が与えられる.
$1$ つの部屋を借りると最大で $M$ 人まで収納できる.
また,ある部屋で授業 $i$ を行った後,授業 $j$ を行う場合,清掃時間として間を $C_{ij}$ だけ空けなくてはいけない.
借りなくてはいけない部屋の最小数はいくらか求める問題.
$N \leq 100$
$0 \leq A_k \leq B_k \leq 10^7$
$0 \leq C_{ij} \leq 10^7$
$1 \leq M, S_k \leq 10^5$

解法

DAGの最小パス被覆の変形版.
それぞれの授業に必要な教室数 $\lceil S_k / M \rceil$ は先に計算しておく.
 すべての授業を別の教室を用いた場合の必要数 - 使いまわした教室ののべ数
で答えを計算する.
使いまわせる最大数は,最大流で求めることができる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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