我试图从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完成此任务的算法 .
1 回答
在整个网络上使用Floyd-Fulkerson来计算最大流量，该最大流量将由k个边缘不相交的路径组成 .
由于已经删除了正好k个边缘，并且所有流都被切断，因此必须沿着这些路径中的每个路径删除一条边 .
对于每个最多包含n个边的路径，使用O（log n）ping到路径上的节点，进行二进制搜索以发现断边的位置 .