楼主:
GYLin (Lynx)
2019-03-09 08:59:53由于是现实的问题 所以有没有P的解我也不知道
还请各位见谅
问题如下:
有N个人(N<=60)参加面试
有M个部门(M=7)可以选
面试时间有T个(T=6)
每个人可以选1~3个部门面试
且每个人各有可以的时间(1~T之中任意选取)
======
想请问考虑所有部门的各时段(M*T个),
他们之中人数最大值, 最少可以是多少, 能让所有人排到面试.
(各个人想面试的每个部门都要能面试到)
======
如果每个人只能选择一个部门, 我有想到最大流的解法,
从原点流向每个人, 再从每个人流向M*T个时段,
调整各时段的出容量, 逐次加一, 当总流量=人数,
此出容量即为解.
但是当一个人可以面试多个部门, 我卡在一个人同时间不能出现在两地,
不知道能不能依然用最大流解...
作者: lancerd (lancerW) 2019-03-16 01:07:00
“每个人可以选1~3个部门面试”是说“每个人各自选好部门了，部门数量最多是三个”，还是说你的答案要让“每个人随便选三个部门”的所有情况都满足？