將圖書館書籍分配給成員以使最大成員滿意的算法

Question

我在班級測試中遇到了問題。在一個圖書館裏，每個成員要求四本書和每本書只有兩個成員要求。此信息在二分圖G =（X + Y，E）的形式給出

X：設置所有成員 的Y：設置的所有書籍 邊緣E =邊集（X，Y），其中x是書y所要求的成員。 我們必須找到圖書管理員可以給每個成員最多兩本書的方式，以使最大成員滿意。

我想出了兩種方法：

1. 引入了兩個新的頂點S（源）和T（目標）。將邊從s引入到X中容量爲2的所有成員中。所有邊E具有容量1，新邊Y到t具有容量1.現在應用Max流算法來查找最大匹配。最大匹配是所需的解決方案。
2. 另一種方法是通過引入相同的邊緣來遵循上述相同的算法，但每個邊緣的容量爲1。現在找到最大匹配。這種匹配會給最多成員一本書。刪除匹配的書籍，並再次應用以上算法。再次刪除匹配的書籍和有兩本書的成員，並再次應用算法，直到X和Y之間沒有邊緣。達到的解決方案是所需的解決方案。

雖然我得到了以上的算法，但我不知道哪個是正確的或沒有正確的。如果有其他算法，請在這裏建議。

Answer 1

第一個看起來是正確的。與第二個，你不能保證你的第一輪書籍任務不會阻止你達到最佳狀態。