我阅读了维基百科和TopCoder上对应的文章，但其中的内容几乎毫无意义。
编辑：在阅读幻灯片并仔细重新阅读TopCoder文章后，我仍然不明白何时以及如何进行重新标记。
推-重贴标签最大流算法是如何工作的？
4
- Alexandros
8
不，我不完全理解算法。 - Alexandros
TopCoder上的教程http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel，实际上非常好。此外，在http://www.imada.sdu.dk/~jbj/DM85/preflownew.pdf上还有一个非常好的幻灯片解释。但是，如果您没有任何图论和图算法的先前经验，那么理解起来可能会很困难。在TopCoder页面底部有一些链接，可以帮助您理解基本概念。 - Joel Lee
阅读幻灯片和仔细再次阅读TopCoder文章后，我仍然不明白何时以及如何进行重新标记。 - Alexandros
另一个解释。http://serverbob.3x.ro/IA/DDU0164.html#ch26ex40 - Tim Lovell-Smith
您可以阅读算法的直觉/类比，其中“推送”操作涉及将流从上游推向下游，而“重新标记”操作涉及提高顶点，以便过剩流量可以通过未饱和弧线传递给其邻居。它维护的“预流”最终将成为有效流，也是最大流。 - Ivan Xiao
显示剩余3条评论
1个回答
2
为了理解推-重贴算法，您需要理解推和重贴操作。该算法会迭代运行它们，只要有可能。此外，在算法执行过程中有时网络流并不是有效的，但最终会变得有效。
推（节点）
推操作检查流是否进入一个节点比离开它更多，并且如果某些剩余容量在该节点的某些出边中，则有可能流出这些超额流。
重贴（节点）
重贴操作接收不能离开的节点进入的超额流，因为所有出边都饱和了，然后通过向后传播进入边来减少其流出量。通常这是通过存储与每个节点相关联的势或高度来完成的，并且确保流始终沿势函数下降。
推（节点）
推操作检查流是否进入一个节点比离开它更多，并且如果某些剩余容量在该节点的某些出边中，则有可能流出这些超额流。
重贴（节点）
重贴操作接收不能离开的节点进入的超额流，因为所有出边都饱和了，然后通过向后传播进入边来减少其流出量。通常这是通过存储与每个节点相关联的势或高度来完成的，并且确保流始终沿势函数下降。
- nickponline
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接