louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共1篇）

题解 | 算法竞赛进阶指南 Vani和cl2捉迷藏

思路事实上,此题等价于求最小路径可重覆盖.为什么呢?我们可以考虑构造出所有的藏身点.首先,跑一遍最小路径可重覆盖后,将所有路径的终点加入集合.假设表示.表示传递闭包后的边集.如果,选取,不断沿着路径向前移,直到为止.不断重复以上过程,直到停止.容易证明,这样肯定能找到一个合法的方案.这题不需要输出...

Floyd 最小路径覆盖

2019-08-24

0 645