algorithm - Skiena 算法设计

Question

我在 Skiena 的算法设计中遇到了一个问题。我不知道我的解决方案是否正确。

5-18。考虑一组电影 M_1、M_2、.. M_k。有一组客户，每个客户都表示他们想在这个周末看的两部电影。电影在周六晚上和周日晚上放映。可以同时放映多部电影。您必须决定哪些电影应该在周六播出，哪些电影在周日播出，这样每个客户都可以看到他们想要的两部电影。是否有每部电影最多放映一次的时间表？设计一种有效的算法来找到这样的时间表（如果存在）。

解决方案：我们有一组电影{M1,M2..Mk}和一组{C1,C2,..Cp}给客户。我们连接C1想要观看的边缘2电影，连接边缘2电影C2 想看的电影等等。这组电影变成了一个连通图。我想验证它是否是一个二分图，比如不能在同一晚放映 2 部喜欢的电影（将 2 部喜欢的电影用不同的颜色着色） .如果是，我们会在星期六显示所有以第一种颜色着色的电影，在星期日显示第二种颜色的所有电影。问题解决了。但如果不是我该怎么办？

Answer 1

从电影 M1、M2、...、Mk 创建一个图表。如果客户指定 Mi 和 Mj，我们在 Mi 和 Mj 之间放置一条边。对所有客户重复此操作。然后使用双色算法将电影分成两组，一组是星期六，一组是星期天。

Answer 2

问题提到我们可以同时放映电影。采取两组周六和周日。对于每个客户，检查他想看的电影是否在不同的场景中，如果它们不是在周六随机放一部，在周日放一部，然后继续。如果它们在同一个集合中，则将它们中的任何一个放在另一个集合中。在最坏的情况下，每部电影都将在周六和周日放映。