[問題] 一題現實中的問題

[GYLin (Lynx)]

由於是現實的問題 所以有沒有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://www.ptt.cc/bbs/Prob_Solve/M.1552093196.A.728.html
※ 編輯: GYLin (36.226.98.184), 03/09/2019 09:02:17
推 FRAXIS: 最大人數最小值 <- 你是說部門人數嗎？
是每個部門的每個時段 所以有T*M個 使當中的最大值最小
→ FRAXIS: 如果是實務上的問題 就建一個 integer programm 來解吧
忘了還有這步可以用 感謝大大
不過還是有點好奇能不能用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
推 FRAXIS: 因為每個人頂多只能面試三次 所以你只要用C(TM, 3) 個
→ FRAXIS: node 就可以表示 constraint ？
這樣可以避免同一個人時間衝到 但這樣每個node流入流出的量好像就不一定相等了?
※ 編輯: GYLin (36.226.98.184), 03/10/2019 22:38:16
推 FRAXIS: 我不懂你的意思 流入和流出量不等還叫做 flow 嗎？
對啊 我的意思是 用 C(T*M, 3) 個點
那這些點的流入量我猜就是每個人的選擇, 流出應該就是再流到T*M個node
分別代表T*M個時段分別被用到了幾次
但是這樣的話, 做了一個選擇, 流出量卻有可能需要三倍, 就無法使用flow了
勢必要有其他建圖方法, 但我還沒想到就是了
※ 編輯: GYLin (36.226.98.184), 03/11/2019 09:59:49
推 FRAXIS: C(T*M, 3) 流入跟流出的 capacity 都是 1
→ FRAXIS: T*M個node 流入 capacity 1 流出 capacity 3
→ FRAXIS: 這樣可行嗎？
推 LPH66: flow 不會複製, 所以樓上那樣的 cap 3 永遠只會滿足至多 1
→ LPH66: 原 PO 現在的問題就是在這裡
推 FRAXIS: 喔喔 我想錯了
推 lancerd: 「每個人可以選1~3個部門面試」是說「每個人各自選好部門
→ lancerd: 了，部門數量最多是三個」，還是說你的答案要讓「每個人
→ lancerd: 隨便選三個部門」的所有情況都滿足？
→ GYLin: 謝謝LPH大大解釋，回樓上是前者