Private Teacher の解説
問題作成者:
野田
解答作成者: 荒木、林崎、八森
英訳:
八森
解説:
八森
概要
 家庭教師がN人の生徒を受け持っている。
 W週間でそれぞれの生徒に必要なだけの
授業をしなくてはならない。
 それぞれの生徒の都合のよい曜日に
授業をしなくてはならない。
 生徒全員に必要なだけの授業ができるか？
解法
 最大フロー問題として解く.
 スーパーソース、スーパーシンク、
全生徒、各曜日に対応するノードを用意する。
 スーパーソースから各生徒へのエッジの容量を
必要な授業数とする.
 各生徒から都合がいい曜日に対してのみエッジの容量を
∞にする.
 各曜日からスーパーシンクへのエッジの容量を
残り週数とする.
 前述のグラフ上で最大フローの
アルゴリズムを走らせて、最大フローの
値が全生徒の必要な授業数となっていれ
ばYes, そうでなければ Noを出力.
 Sample Inputの一つ目をグラフにするとこうなる
∞
∞
生徒１
6
source
∞
∞
8
生徒２
∞
∞
∞
月
火
水
木
2
2
2
2
2
金
土
日
2
2
sink
注意点
 W（残り週数）は10^10まである。
なのでintだとオーバーフローする。
Submit状況
 Submit数: 20
 Accepted数: 7
 最速Accepted: 90分 (Unknown)

第 139 回 2/22(日)日商簿記検定3級

第 138 回 11/16(日)日商簿記検定3級

rummy

Document