P13489 [GCJ 2008 Finals] Bridge Builders

Rigel · 2025-09-17 10:29:27 · 题解

思路

首先计算出任意两个可达格子（除海洋以外的格子）之间的距离。在所有可达格子和与其四方向相邻的可达格子之间连边，边权为 1。从每个格子开始跑 Dijkstra，求出任意两个格子之间的最短路，即它们之间的距离。

先不考虑森林之间的连通情况，假设每个普通岛屿只需与任一森林连通。不难得出，对于每个普通岛屿，将其连通的最小费用为它与离它最近的森林的距离。

然后考虑将所有森林连通。

对于森林 u,v，需要计算出将它们相连的额外费用 w。

设 u,v 的距离为 d。

当 d \mod 2 = 0 时，如图所示，蓝色为将普通岛屿连接至森林的费用，红色为原图中的格子均未连通时连通 u,v 的费用。

此时额外费用 w = \dfrac{(\dfrac{d}{2} + 1 + d) \times \dfrac{d}{2}}{2} - \dfrac{(1 +\dfrac{d}{2} - 1) \times (\dfrac{d}{2} - 1)}{2} = \dfrac{d^2}{4} + \dfrac{d}{2}。

当 d \mod 2 = 1 时，如图所示。

此时额外费用 w = \dfrac{(\lfloor \dfrac{d}{2} \rfloor + 1 + d) \times (\lfloor \dfrac{d}{2} \rfloor + 1)}{2} - \dfrac{(1 +\lfloor \dfrac{d}{2} \rfloor) \times \lfloor \dfrac{d}{2} \rfloor}{2} = \dfrac{(d+1)(\lfloor \dfrac{d}{2} \rfloor + 1)}{2}。

综上，额外费用 $ w = \begin{cases} \dfrac{d^2}{4} + \dfrac{d}{2} & d \mod 2 = 0,\ \ \dfrac{(d+1)(\lfloor \dfrac{d}{2} \rfloor + 1)}{2} & d \mod 2 = 1. \end{cases}