网络流算法相关问题
Network flow algorithm related problems
我正在尝试解决来自 tardos 的以下问题。如有任何建议或帮助，我们将不胜感激。
您被要求帮助一些网络管理员诊断其网络故障的程度。该网络旨在将流量从指定的源节点 s 传送到指定的目标节点 t，因此我们将其建模为有向图 G = (V,E)，其中每条边的容量为 1，其中每个节点位于从 s 到 t 的至少一条路径上。
现在，当网络中的一切 运行 顺利时，G 中的最大 s-t 流的值为 k。然而，目前的情况 - 以及你在这里的原因 - 是攻击者已经破坏了网络中的一些边，因此现在没有使用剩余（幸存）边从 s 到 t 的路径。由于我们不会在这里讨论的原因，他们认为攻击者只破坏了 k 边，这是将 s 与 t 分开所需的最小数量（即最小 s-t 切割的大小）；我们假设他们相信这一点是正确的。
网络管理员是 运行 节点 s 上的一个监控池，它具有以下行为：如果您发出命令 ping(v)，对于给定的节点 v，它会告诉您当前是否有来自 s 的路径到 v.（所以 pint(t) 报告当前不存在路径；另一方面，ping(s) 总是报告从 s 到它自己的路径。）因为出去检查网络的每个边缘是不切实际的，他们想通过明智地使用 ping 命令来确定使用此监视工具的故障程度。
所以这就是您面临的问题：给出一个算法，该算法向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过对网络中的每个节点执行 ping 操作来执行此操作，但您希望使用更少的 ping 操作来执行此操作（假定仅删除了 k 条边）。在发出此序列时，允许您的算法根据先前 ping 操作的结果来决定下一个要 ping 的节点。
给出一个仅使用 O(k log n) 次 ping 即可完成此任务的算法。
在完整网络上使用 Floyd-Fulkerson 计算最大流量，它将由 k 条边不相交的路径组成。
由于正好删除了 k 条边，并且所有流都被切断，因此必须沿着这些路径中的每条路径恰好删除一条边。
对于最多包含 n 条边的每条路径，对路径上的节点使用 O(log n) 次 ping 进行二进制搜索以发现断边的位置。
我正在尝试解决来自 tardos 的以下问题。如有任何建议或帮助，我们将不胜感激。
您被要求帮助一些网络管理员诊断其网络故障的程度。该网络旨在将流量从指定的源节点 s 传送到指定的目标节点 t，因此我们将其建模为有向图 G = (V,E)，其中每条边的容量为 1，其中每个节点位于从 s 到 t 的至少一条路径上。
现在，当网络中的一切 运行 顺利时，G 中的最大 s-t 流的值为 k。然而，目前的情况 - 以及你在这里的原因 - 是攻击者已经破坏了网络中的一些边，因此现在没有使用剩余（幸存）边从 s 到 t 的路径。由于我们不会在这里讨论的原因，他们认为攻击者只破坏了 k 边，这是将 s 与 t 分开所需的最小数量（即最小 s-t 切割的大小）；我们假设他们相信这一点是正确的。 网络管理员是 运行 节点 s 上的一个监控池，它具有以下行为：如果您发出命令 ping(v)，对于给定的节点 v，它会告诉您当前是否有来自 s 的路径到 v.（所以 pint(t) 报告当前不存在路径；另一方面，ping(s) 总是报告从 s 到它自己的路径。）因为出去检查网络的每个边缘是不切实际的，他们想通过明智地使用 ping 命令来确定使用此监视工具的故障程度。 所以这就是您面临的问题：给出一个算法，该算法向网络中的各个节点发出一系列 ping 命令，然后报告当前无法从 s 访问的完整节点集。当然，您可以通过对网络中的每个节点执行 ping 操作来执行此操作，但您希望使用更少的 ping 操作来执行此操作（假定仅删除了 k 条边）。在发出此序列时，允许您的算法根据先前 ping 操作的结果来决定下一个要 ping 的节点。 给出一个仅使用 O(k log n) 次 ping 即可完成此任务的算法。
在完整网络上使用 Floyd-Fulkerson 计算最大流量，它将由 k 条边不相交的路径组成。
由于正好删除了 k 条边，并且所有流都被切断，因此必须沿着这些路径中的每条路径恰好删除一条边。
对于最多包含 n 条边的每条路径，对路径上的节点使用 O(log n) 次 ping 进行二进制搜索以发现断边的位置。