[QkOI#R1] Quark and Flying Pigs 官方题解

LCuter · 2020-05-03 17:59:53 · 题解

B - Quark and Flying Pigs

\text{Description}

给定一个 n 个点 m 条边的边带权无向图，在 0 时刻你在点 1 上。

假设当前是 t 时刻，你在点 v 上，你可以选择两种操作：

• 仍停留在点 v 上，操作后到 t+1 时刻。
• 选择一条边 (a,b,w) 满足 a=v 或 b=v，则你到这条边连接的另一个点上，操作后到 t+w 时刻。

有 k 条信息，每一条信息形如 (t_i,v_i) 表示在 t_i 时刻，点 v_i 上会出现一只飞猪，其编号为 i，若该时刻你在 v_i 上，则你捕获到了 i 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

先跑一遍 Floyd 求出任意点对间最短路。

接下来将每条信息按 t_i 从小到大排序，设 f_i 表示在只考虑前 i 个信息时能捉到的飞猪数量，则有：

时间复杂度 O(k^2+n^3)。

好像和 P2285 撞题了。

Flying Pig 就是（数据删除）