[問題] 求問一題Maximum Flow?

[Emmanuel (天馬)]

一個演算法的問題：
假設我要將x個學生"平均"分配給y個老師(x>y)，其中每個學生跟老師之間都有一個適合
度Kx,y，我希望分配後，合作度加總能夠最大，有人知道怎麼解嗎？
我在想Maximum Flow或DP能不能解這個問題，如果沒有限制要平均分配(每個老師管到一
樣多的學生)，這題用Maximum Flow應該就可以解了，但加上這個條件的話呢？

另外如果有人對分配的演算法很熟悉或有興趣，也歡迎討論，thanks!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.98 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1605685318.A.690.html
推 ucrxzero: 感覺要五維DP
推 ucrxzero: 更正 三維
推 ucrxzero: 好像一維就好了
→ ucrxzero: 先更正 二維
→ ucrxzero: 我回去再想 再吃飯
推 ucrxzero: 問你哦 如果窮舉所有平均人數的組合在用你說的maximum
→ ucrxzero: flow 可以接受嗎？
→ ucrxzero: 至少不是從頭到尾無腦窮舉
推 ucrxzero: 先從一個學生一個老師思考試試看
推 ucrxzero: 一邊吃飯應酬一邊想太難了回去再想
→ ucrxzero: 反正不能用互斥窮舉就對了
→ ucrxzero: ？
→ Emmanuel: 窮舉 是列出所有可能的組合？那會很慢誒
推 ucrxzero: bipartite graph???
→ Emmanuel: 目前有想到作法了，但可能也蠻慢的，DP有幾個細節還沒想
→ Emmanuel: 清楚
推 ucrxzero: Maximum Bipartite Matching
→ ucrxzero: GeeksforGeeks 這個應該蠻像的
→ Emmanuel: 我一開始也是想到那個
→ Emmanuel: 但應該不太一樣
推 ucrxzero: 等高手解答吧