我在课堂测试中遇到了一个问题。在图书馆里，每个成员要四本书，而每本书只有两个成员要。此信息以二分图 G = ( X + Y , E ) 的形式给出
X：所有成员的集合 Y：所有书籍的集合 Edge E = 边的集合 (x,y)，其中 x 是为书籍 y 请求的成员。我们必须找到图书馆员最多可以给每个成员两本书的方式，以使最多的成员满意。
我提出了两种方法：
- 引入两个新顶点 s(source) 和 t(destination)。将边从 s 引入 X 中容量为 2 的所有成员。所有边 E 的容量为 1，新边 Y 到 t 的容量为 1。现在应用 Max flow 算法找到最大匹配。最大匹配是所需的解决方案。
- 另一种方法是通过引入相同的边来遵循与上述相同的算法，但每条边的容量为1。现在找到最大匹配。此匹配将为最多成员提供一本书。删除匹配的书籍并再次应用上述算法。再次删除匹配的书籍和拥有两本书的成员，并再次应用算法，直到 X 和 Y 之间没有边缘。获得的解决方案是所需的解决方案。
虽然我得到了上面的算法，但我不确定哪个是正确的，或者没有一个是正确的。如果还有其他算法，请在此处提出建议。