algorithm - Professor Adam's Kids(确定最大流量)

Question

我需要帮助来理解如何解决以下问题:

Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any block that the other child has stepped on that day. The children have no problem with their paths crossing at a corner. Fortunately both the professor's house and the school are on corners, but beyond that the professor is not sure if it is going to be possible to send both of the children to the same school. The professor has a map of the town. Show how to formulate the problem of determining whether both the children can go to the same school as a maximum-flow problem.

我唯一能想到的就是有一个四角图。左上角的顶点代表源(亚当的房子)，右下角代表汇(学校)。右上角的角 x 表示邻域中的角，而 y 表示邻域的左下角。因此，我们的路径从 S -> C1、S -> C2、C1 -> t 和 C2 ->吨。每条路径的权重为 1，因为它只能容纳一个 child 。该图的最大流量为 2，证明他们可以就读同一所学校。

我遇到的问题是我不确定我找到的这个解决方案是否能解决问题。最让我难过的部分是，我不确定这意味着什么:但实际上每个人都拒绝走另一个 child 当天踩过的任何障碍物。这句话怎么能如果他们都住在同一街区的同一所房子里，这有意义吗？

Answer 1

更新:原来，我误读了问题。该问题要求找到“边不相交”的路径，而不是顶点不相交的路径。在这种情况下，解决方案只是将每个角表示为一个顶点，将每个 block 表示为容量为 1 的边，并运行常规最大流(正如下面 Curious 所正确建议的那样)。

我相信那个 OP 有同样的困惑基于

but in fact each one refuses to walk on any block that the other child has stepped on that day. How can this statement make sense if both live in the same house on the same block?

请注意， children 住在同一个角落的同一所房子里，而不是同一个街区。

我留下剩下的答案，以防有一天有人真的在寻找顶点不相交的问题:

---

如果我对问题的理解正确，它要求的是找到从源到汇的两条顶点不相交的路径。仅按原样使用图，并为每条边分配 1 的容量是不够的。考虑以下示例:

s -> C1, C1 -> C3, C3 -> C4, C4 -> t
s -> C2, C2 -> C3, C3 -> C5, C5 -> t

如果您为这些边中的每一个分配 1 的容量，并运行任何最大流算法，它会发现最大流为 2，但是没有两个顶点不相交的路径(两条路径都会通过顶点 C3)。

要解决这个问题，您需要调整图表。对于除 s 和 t 之外的每个顶点，将其一分为二。假设顶点 u 被拆分为 u' 和 u''。使所有进入 u 的边都进入 u'，所有从 u 开始的边都从 u ''(那些边的容量无关紧要，只要是正数即可，所以可以设置为1)。最后，添加一条从 u' 到 u'' 的边，容量为 1，并在此图上运行最大流。由于我们在拆分节点之间添加的那些边，每个顶点最多使用一次，因为对于要使用的顶点，我们需要输入 u'，从 u' 到 u'' 并从那里退出，只有一个单位的流量可以从 u' 到 u''。