作者:
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個部門面試」是說「每個人各自選好部門了，部門數量最多是三個」，還是說你的答案要讓「每個人隨便選三個部門」的所有情況都滿足？