algorithm - 如何解决这个算法问题 - Gopher 2

Question

我正在尝试解决这个问题https://open.kattis.com/problems/gopher2：

避免了犬类威胁的地鼠家族必须面对新的捕食者。

它们是地鼠和地鼠洞，每个都在不同的 (,) 坐标上。一只鹰来了，如果一只地鼠没有在几秒钟内到达一个洞，它很容易被吃掉。一个洞最多能救一个地鼠。所有的地鼠都以相同的速度运行。gopher 家族需要一种逃生策略，以尽量减少易受攻击的 > > gopher 的数量。

t 最小化易受攻击的地鼠的数量。

蛮力方法是找到每个地鼠可到达的所有可能的洞，然后找到所有不同的（地鼠，洞）对。

有更快的算法吗？

标签： algorithmgreedy

Answer 1

这可以表述为二分图上最大基数匹配问题的一个实例。

让我们A成为一组地鼠，B成为一组洞。如果它们之间的距离最多为，则从地鼠a ∈ A到洞有一条边，即地鼠在可用时间内可以运行的最大距离。b ∈ Bs*v

解决方案由该图中边的最大尺寸子集组成，使得 (1) 每个a ∈ A都最多有一个边，(2) 每个b ∈ B人最多有一个边。约束表示每个地鼠只能去一个洞的规则，每个洞只能适合一个地鼠。“易受攻击”地鼠的数量就是地鼠的数量减去匹配中的边数。

该图需要 O( mn ) 时间来构建，并且可以使用标准算法（例如Ford-Fulkerson ）在 O( mn ) 时间或更短的时间内找到最大基数匹配，其中m是地鼠的数量，n是地鼠的数量孔。

如果这对在线法官来说不够有效，您可以使用更有效的算法来查找匹配，并使用更有效的方法来查找图中的边，例如使用四叉树查询哪些孔在距离范围s*v内在 O( n ) 时间内地鼠。