作者GYLin (Lynx)
看板Prob_Solve
标题[问题] 一题现实中的问题
时间Sat Mar 9 08:59:53 2019
由於是现实的问题 所以有没有P的解我也不知道
还请各位见谅
问题如下:
有N个人(N<=60)参加面试
有M个部门(M=7)可以选
面试时间有T个(T=6)
每个人可以选1~3个部门面试
且每个人各有可以的时间(1~T之中任意选取)
======
想请问考虑所有部门的各时段(M*T个),
他们之中人数最大值, 最少可以是多少, 能让所有人排到面试.
(各个人想面试的每个部门都要能面试到)
======
如果每个人只能选择一个部门, 我有想到最大流的解法,
从原点流向每个人, 再从每个人流向M*T个时段,
调整各时段的出容量, 逐次加一, 当总流量=人数,
此出容量即为解.
但是当一个人可以面试多个部门, 我卡在一个人同时间不能出现在两地,
不知道能不能依然用最大流解...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.226.98.184
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1552093196.A.728.html
※ 编辑: GYLin (36.226.98.184), 03/09/2019 09:02:17
1F：推 FRAXIS: 最大人数最小值 <- 你是说部门人数吗？ 03/09 12:06
是每个部门的每个时段 所以有T*M个 使当中的最大值最小
2F：→ FRAXIS: 如果是实务上的问题 就建一个 integer programm 来解吧 03/09 12:08
忘了还有这步可以用 感谢大大
不过还是有点好奇能不能用flow就是了
※ 编辑: GYLin (36.226.98.184), 03/09/2019 13:43:20
※ 编辑: GYLin (36.226.98.184), 03/09/2019 13:44:53
※ 编辑: GYLin (36.226.98.184), 03/09/2019 13:45:44
3F：推 FRAXIS: 因为每个人顶多只能面试三次 所以你只要用C(TM, 3) 个 03/10 06:35
4F：→ FRAXIS: node 就可以表示 constraint ？ 03/10 06:35
这样可以避免同一个人时间冲到 但这样每个node流入流出的量好像就不一定相等了?
※ 编辑: GYLin (36.226.98.184), 03/10/2019 22:38:16
5F：推 FRAXIS: 我不懂你的意思 流入和流出量不等还叫做 flow 吗？ 03/11 06:23
对啊 我的意思是 用 C(T*M, 3) 个点
那这些点的流入量我猜就是每个人的选择, 流出应该就是再流到T*M个node
分别代表T*M个时段分别被用到了几次
但是这样的话, 做了一个选择, 流出量却有可能需要三倍, 就无法使用flow了
势必要有其他建图方法, 但我还没想到就是了
※ 编辑: GYLin (36.226.98.184), 03/11/2019 09:59:49
6F：推 FRAXIS: C(T*M, 3) 流入跟流出的 capacity 都是 1 03/11 10:46
7F：→ FRAXIS: T*M个node 流入 capacity 1 流出 capacity 3 03/11 10:46
8F：→ FRAXIS: 这样可行吗？ 03/11 10:46
9F：推 LPH66: flow 不会复制, 所以楼上那样的 cap 3 永远只会满足至多 1 03/14 18:11
10F：→ LPH66: 原 PO 现在的问题就是在这里 03/14 18:11
11F：推 FRAXIS: 喔喔 我想错了 03/15 11:10
12F：推 lancerd: 「每个人可以选1~3个部门面试」是说「每个人各自选好部门 03/16 01:07
13F：→ lancerd: 了，部门数量最多是三个」，还是说你的答案要让「每个人 03/16 01:07
14F：→ lancerd: 随便选三个部门」的所有情况都满足？ 03/16 01:07
15F：→ GYLin: 谢谢LPH大大解释，回楼上是前者 03/16 13:16