![解法
source から 各使い魔に[M/N,M/N+(M%N==0?0:1)]の流量の辺をはる
各悪魔から sink に流量1で辺をはる
使い魔
悪魔
s t
[M/N,M/N+(M%N==0?0:1)]](https://image.slidesharecdn.com/a6qqtu3rrbco7qnxenk3-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125739/85/RUPC2017-J-6-320.jpg)
![解法
フローを流して M だけ流れるかチェックする。
使い魔
悪魔
s t
[0,1]](https://image.slidesharecdn.com/a6qqtu3rrbco7qnxenk3-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125739/85/RUPC2017-J-7-320.jpg)
![解法
ここをなんとかする必要がある。（これはやり方がいくつかある）
使い魔
悪魔
s t
[0,1]](https://image.slidesharecdn.com/a6qqtu3rrbco7qnxenk3-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125739/85/RUPC2017-J-8-320.jpg)
搁鲍笔颁2017:闯解説
- 1. デモンズプラン 原案：public_sate テスター：haji / uku / gacho
- 2. 問題概要 ● N体の使い魔とM体の悪魔がいます。 ● 各使い魔と悪魔の距離が与えられます。 ● かならず全ての悪魔にちょうど１体の使い魔が訪問しなければならない。 ● 使い魔は複数の悪魔を訪問できる。 ● 以下の条件を満たす使い魔と悪魔の割り振り方をしてください。 a. 使い魔1体あたりの訪問する悪魔の数の差の最大を最小化する。 b. aを満たした上で訪問する悪魔と担当する使い魔の距離の最大を最小 化する。
- 6. 解法 source から 各使い魔に[M/N,M/N+(M%N==0?0:1)]の流量の辺をはる 各悪魔から sink に流量1で辺をはる 使い魔 悪魔 s t [M/N,M/N+(M%N==0?0:1)]
- 7. 解法 フローを流して M だけ流れるかチェックする。 使い魔 悪魔 s t [0,1]
- 10. 解法（やりかた１） S1 から t にめいいっぱい流す。これがmin * N 以下であれば false。 false なのは全ての使い魔が最低限の仕事をしていないため。 使い魔 悪魔 S 2 t S 1 min max-min
- 11. 解法（やりかた１） 先程最低限を流しきった状態から S2 から t にめいいっぱい流す。これが M - min*Nであれば true。 使い魔 悪魔 S 2 t S 1 min max-min
- 16. 結果 ● Onsite and Online ○ First Submission : biwako_sen (2h16min) ○ First Accept : caffe (3h18min) ● SuccessRate (Accept/Submission) ○ 21.43 %
- 17. ジャッジ解 sate c++ 112行 haji c++ 87行 uku c++ 119行 gacho c++ 76行