如何在PHP中实现三维二部匹配算法

Question

我需要实现一个三维二部匹配算法。这段代码是一种二维二部匹配算法。我已经能够将它转换成PHP，并且它工作得很好。然而，我刚刚意识到，在我的程序中，我需要将课程与房间匹配，以适应特定的时隙。如果我使用二维二部匹配算法，已经分配的房间不能用于其他时隙中的课程。我想有一个匹配，在同一房间可以再次用于另一个课程，一旦时间是不同的。我如何修改这个代码作为输入一个三维图形:图，其中u当然是索引，v是房间的索引，w是时隙的索引。

Answer 1

二部匹配不是这样的。“‘Bi”的意思是两个。但是，您可以很容易地将图转换为二分图。不要去思考左边的课程和右边的房间，而是这样想--课程仍然在左边，但是右边是房间和时隙的节点。就像这样-

Course CSE 101------Room 301 Time 10:00 - 11:00
              \
               \
                \               
                 \
                  \
Course CSE 145------Room 301 Time 11:00 - 12:00
              \
               \
                \            
                 \
                  \-Room 301 Time 12:00 - 13:00 

如果你正在研究一个现实世界的问题，还会有其他的限制，比如一周内为一门课程分配3个教室，同一课程的两个班不应该在同一天上课等等。在这种情况下，你必须从图的二分模型转移到一般的流网络。