P6573 [BalticOI 2017] Toll 题解

· · 题解

最短路矩阵

注意到题目中有 \left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor 这个性质。

不难发现这个图可以每 k 个点分一层，每层只有连向下一层的边。

可以发现每一层到下一层的最短路构成了一个 k\times k 的矩阵。

设第 i 层到 i+1 层的最短路矩阵为 A，设第 i+1 层到 i+2 层的最短路矩阵为 B。

矩阵计算

那么从设第 i 层到 i+2 层的最短路矩阵 C 可以用 C_{i,j}=\min\limits_{x=1}^k A_{i,x}+B_{x,j} 求出。

这是一个 [+,\min] 矩阵，满足交换律和结合律。

构造完矩阵后，答案就是第 \left\lfloor\dfrac{a}{k}\right\rfloor 层到第 \left\lfloor\dfrac{b}{k}\right\rfloor 层最短路矩阵 M 中的 M_{a\bmod k,b\bmod k}。

计算矩阵

接下来就是如何计算第 \left\lfloor\dfrac{a}{k}\right\rfloor 层到第 \left\lfloor\dfrac{b}{k}\right\rfloor 层最短路矩阵 M。

观察到可以把 \left\lfloor\dfrac{a}{k}\right\rfloor\sim \left\lfloor\dfrac{b}{k}\right\rfloor 拆成很多段，这样可以用倍增的思想解决。

设 f_{i,j} 为第 i 层到 i+2^j 层的最短路矩阵，转移直接用 f_{i,j}=f_{i,j-1}\times f_{i+2^{j-1},j-1}。

把 \left\lfloor\dfrac{a}{k}\right\rfloor\sim \left\lfloor\dfrac{b}{k}\right\rfloor 进行二进制拆分，就可以解决。

细节问题

数据中有 \left\lfloor\dfrac{a}{k}\right\rfloor=\left\lfloor\dfrac{b}{k}\right\rfloor 的数据，需要特判。

这题的空间只有 128MB，如果 MLE 可以尝试把数组开小。