模型流网络

Question

有n个人，其中一些人持有钥匙。有⌈n/5⌉门，要打开每扇门，至少要有两个有钥匙的人在门口。最多5个人可以去一扇门，每个人只能去他们能到达的一扇门，每个人必须去一扇门，所以没有人掉队。我如何将这个问题建模成一个流网络，以便找到打开所有门的人员分配（满足约束的任何组合）？

我有一个像下面这样的模型。有人节点和门节点。

连接源到每个人员节点的边的容量为 1。

连接人节点和门节点的边的容量为1，每个人连接到1个或多个门（他们可以到达的门）。

连接门节点和水槽的边的容量为 5，下限为 2，因为最多 5 人可以进入一扇门，并且至少有 2 个人拥有钥匙必须在场。

*现在我的问题是如何在密钥中建模。我们知道哪些人有钥匙。

Answer 1

型号

“没有人落后”这是一个困难的优化函数，因为它只有两个值（0或1）。首先，我建议使用“最大化进门的人数”。

“连接门节点和水槽的边的容量为 5，下限为 2”我们需要考虑以下可能性：某些门可能无法由 5 个人到达，并且某些门可能不需要。我建议将这些链接的容量设置为最小值 5 以及可以到达门口的人数，并且没有最小值。

“有人节点”在这个问题中，所有人都是不平等的。有些有钥匙，有些没有。所以你需要两种人员节点。

2阶段贪心算法

第一阶段

• 按递减的价格订购门。 （门值是可以到达门的人数和 5 的最小值）
• 将持有钥匙的人按照价值递减的顺序，两个两个地分配到门上

第二阶段

• 构建流程模型：
  • 没有钥匙的人
  • 拥有钥匙但在第 1 阶段未分配的人员
  • 第一阶段打开的门
  • 链接来源和有能力的人员1
  • 连接人员并打开他们可以通过容量 1 到达的大门
  • 连接敞开的门和容量为 3 的水槽
• 应用标准最大流量算法