Skiena算法设计

Question

Skiena算法设计

4

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

5-18. 考虑一个电影集合M_1，M_2，... M_k。有一组顾客，每个顾客都表明他们想在这个周末看的两部电影。电影在周六晚上和周日晚上播放。多部电影可以同时播放。您必须决定哪些电影应在周六电视播出，哪些应在周日电视播出，以便每个顾客都能看到他们所需的两部电影。是否存在时间表，每部电影最多只播放一次？如果存在这样的时间表，请设计一个高效的算法来查找此时间表。

解决方案：我们有一组 {M1,M2..Mk} 的电影和一组 {C1,C2,..Cp} 的顾客。我们用一条边连接C1想观看的2部电影，用一条边连接C2想观看的2部电影等等。电影集合变成了一个连通图。我想验证它是否为二分图，例如不能在同一晚上播放2部喜欢的电影（用不同的颜色对2部喜欢的电影进行着色）。如果可以，我们将所有用第一种颜色涂色的电影放在星期六播出，第二种颜色则放在星期日播出。问题解决了。但是如果不是呢？

- Mougart

2

如果不是二分图，则无法相应地对电影进行分区，因此输出“日程表不存在”。 - G. Bach

没错，谢谢 Bach！ - Mougart

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yi_ · Answer 1

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

- Prashant · Answer 2

问题提到我们可以同时放映电影。取两个集合Sat和Sun。对于每个顾客，检查他想看的电影是否在不同的集合中，如果不是，则将其中一个随机放在Sat中，另一个放在Sun中并继续。如果它们在同一组中，则将它们中的任何一个放在另一个组中。在最坏的情况下，每部电影都将在Sat和Sun上播放。