亚当教授的孩子们（确定最大流量）

Question

亚当教授的孩子们（确定最大流量）

4

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

亚当教授有两个孩子，不幸的是，他们互相不喜欢。问题严重到他们不仅拒绝一起走路上学，而且实际上每个孩子都拒绝走对方当天走过的任何街区。孩子们在拐角处交叉也没有问题。幸运的是，教授的家和学校都在转角处，但除此之外，教授不确定是否可能将两个孩子送到同一所学校。教授有一张城镇地图。请说明如何将确定两个孩子是否可以去同一所学校的问题制定为最大流问题。

我唯一能想到的是建立一个四角图。左上角顶点代表源（亚当的房子），右下角顶点代表汇（学校）。右上角的顶点x表示社区中的一个角落，y表示该社区的左下角。因此，我们有从S -> C1，S -> C2，C1 -> t和C2 -> t的路径。由于每条路径只能容纳一个孩子，因此每条路径的权重为1。此图的最大流量为2，证明他们可以上同一所学校。

我遇到的问题是，我不确定我得出的解决方案是否满足问题。最困扰我的部分是：实际上每个孩子都拒绝走对方当天走过的任何街区。如果两个孩子住在同一条街区的同一所房子里，这句话怎么说得通呢？

- Jubl

1

我投票关闭此问题，因为它不符合[帮助]指南中定义的编程问题标准。 - Ken White

2

@KenWhite，这不是一个与编程有关的问题吗？Ford-Fulkerson 算法。这是在计算机科学算法教材中发现的一个问题。 - Jubl

14

@KenWhite Software algorithms are on topic on Stack Overflow. 在这种特定情况下，最大流问题（以及对应的福特-福尔克森算法）是适合讨论的话题。 - durron597

2

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Paul Hankin

7

请修改问题标题，以便其他人更容易了解并解决类似的问题。请选用更好的标题。 - Raymond Chen

显示剩余3条评论

5个回答

1

让我们保持简单.. 首要任务。为什么你只限制在他的房子和学校以外的2个角落。问题中没有这样说。

Adam问题的建模可以像这样进行顶点：城镇的所有角落 有向边 ：连接角落的所有道路，双向连接，即如果我们有2个角落p,q，则我们将从p到q和从q到p都有一条边

对于所有边缘(u,v)，c(u,v)=1

现在解决最大流问题，如果它是>=2，则Adam很幸运。

- Curious

0

我从维基百科了解到，我从未听说过最大流问题。

看起来图形(V,E)应该为每个街道交叉口设置一个顶点，为每条街道设置一条边（在交叉口之间）。然后每条边的容量都应为1（就像你说的那样）。当然，如果孩子中的一个到达学校，他们也可以回家（使用“相反图”中的类似路径，其中所有边都被颠倒）。

然后唯一的歧义是：边缘的方向应该是什么？如果图形不需要定向，这可能作为问题的制定方式。

- jayflo

0

维基百科

由于问题指定房子（s）和学校（t）都在街角，我假设街角不算“走过一个街区”，而且问题说他们在街角没有交叉问题，因此例如他们可以一起穿过街道到另一个街区，只要其中一个人走人行道到达另一个街角，另一个人立即穿过街道到达另一个街区。

在这种情况下，流量的限制因素是街区，因此它们必须成为流程图中容量为1的边缘。但是它们连接什么？它们必须连接其他街区。因此，想象一个由9个街区组成的正方形：

1 2 3
4 5 6
7 8 9

在1号街的东南角有一座房子，在5号街的东南角有一所学校。两个孩子都可以穿过街道到达5号街，但只有一个人可以绕着5号街走到对面的学校。另一个人可以直接穿过街道到达4号街，然后到7号街，最后到8号街，在那里可以穿过街道到达5号街拐角处的学校。

所以房子可以到达1、2、4和5号街区。学校可以从5、6、8或9到达。我的第一个想法是将每个街区建模为两个节点，输入和输出，并连接容量为1的边将输入与输出相连。其他节点将通过至少具有2个容量的边相连。您还需要s和t节点。将s连接到1、2、4和5的输入，将5、6、8、9的输出连接到t。然后将街区输出连接到任何角落可以到达的街区的输入上，即1的输出也连接到2、4、5的输入，2、4、5的输出也连接到1的输入。

更简单的思考方式可能是，每个角落都是一个节点，连接着周围方块的输入和输出，并且周围方块的输出与输入相连成为了角落节点。除了连接方块输入和输出的边缘容量为 1，所有边缘都应该至少有容量为 2。这样限制因素就是“走在方块上”。只要最后的流量为 2，他们就可以通过。

因此，让我们简化图表并摆脱我们不使用的方块。一个孩子可以从 s 到 t 绕过 5 号方块，另一个孩子可以穿过街道到达 4 号方块，然后在 a 角处穿过到 8 号方块，沿着 8 号方块走到 t 角，那里就是学校。

这里是边缘：

s->4in (capacity 2)
s->5in (capacity 2)
4in->4out (capacity 1) // limiter
5in->5out (capacity 1) // limiter
8in->8out (capacity 1) // limiter
4out->s (capacity 2)
4out->a (capacity 2)
5out->s (capacity 2)
5out->a (capacity 2)
5out->t (capacity 2)
8out->a (capacity 2)
8out->t (capacity 2)
a->4in (capacity 2)
a->5in (capacity 2)
a->8in (capacity 2)

一个孩子的路径 s->5in->5out->t

另一个孩子的路径 s->4in->4out->a->8in->8out->t

- Jason Goemaat

-3

我也在寻找解决方案，发现了这个，看起来对我来说是正确的。

http://www.repond.ch/ressources/cse/algorithme/week10/exercise7-sol.pdf?PHPSESSID=col0hua0ehpk57givsva99mco4

让我们用以下方式将城市地图建模为图G（V，E）：V包含城镇中的每个角落，E包含道路。更具体地说，我们假设如果城市中有连接角落u和v的道路，则节点u，v属于V之间存在一条边缘。我们假设每条边缘的容量为1。此外，让教授Adam的房子成为源s，学校成为汇t。现在我们可以将问题公式化为最大流问题：边缘（u，v）上的流将表示任何孩子是否已经踏上连接角落u和v的道路。此外，在这种情况下，我们只允许整数流f（u，v）= 1。因此，由于图中每条边缘的容量为c（u，v）= 1，如果流通过一个链接，那么该链接就不能再使用了。这意味着另一个孩子将不会走那条路去上学。现在，如果两个孩子都能上学，这意味着从源（房子）到汇（学校）至少有2个值的流。同样，如果在G中从s到t找到一个最大的整数流，其值至少为2，则两个孩子都可以上学。否则，这将是不可能的。

- Nishant

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

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

- Ishamael · Accepted Answer

更新：事实证明，我误读了问题。问题要求找到"边不相交"的路径，而不是顶点不相交的路径。在这种情况下，解决方案只需将每个角落表示为一个顶点，每个街区表示为一条容量为1的边，并运行常规的最大流算法（正如Curious在下面正确建议的那样）。

我相信原帖作者也有同样的困惑，基于以下内容：

但事实上，每个孩子都拒绝走过另一个孩子当天踩过的任何街区。如果他们都住在同一幢房子的同一个街区，这句话怎么能说得通呢？

请注意，孩子们住在同一幢房子的同一个角落，而不是同一个街区。

我保留剩下的回答，以防将来有人实际寻找顶点不相交问题：

如果我正确理解了问题，那么它要求从源到汇点找到两条不相交的路径。仅使用图形，并将每个边缘的容量分配为1是不够的。考虑以下例子：

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

如果你对每条边分配1的容量，并运行任何最大流算法，它将找到最大流为2，但没有两条顶点不相交的路径（两条路径都将通过顶点C3）。

为了解决这个问题，您需要调整您的图形。对于除和之外的每个顶点，将其分成两个部分。假设顶点被分成'和''。使所有进入的边都进入'，所有从出发的边都从''出发（这些边的容量并不重要，只要是正数，所以可以将其设置为1）。最后，在'和''之间添加一条容量为1的边，并在此图上运行最大流。由于我们在分裂节点之间添加了这些边，因此每个顶点最多只能使用一次，因为要使用该顶点，我们需要进入'，从'到''，然后从那里退出，而且只有一单位的流量可以从'到''。