HDUOJ 6331 - Walking Plan

题面

比特城里有 nn 个路口,mm单向街道,第 ii 条街道的长度为 wiw_i。最近小Q计划坚持长走 qq 天:在第 ii 天,小Q计划从 sis_i 路口出发,通过至少 kik_i 条街道并最终到达 tit_i 路口。

虽然小Q看起来很爱运动但其实很懒,所以他希望能使得他每天所走的路程最少。请编写程序计算小Q每一天最少需要走的距离。

数据范围

TT 组测试数据,1T101 \le T \le 10

2n502 \le n \le 50

1m,wi,ki100001 \le m, w_i, k_i \le 10000

题目链接

分析

G[i][j]G[i][j] 代表一步从 iijj 的距离(需要注意的是当 i=ji = jG[i][j]=+G[i][j] = +\infty,因为图中没有自环所以一步是不可能还待在出发点的)。另外,记 f[t][i][j]f[t][i][j] 代表从 ii 出发恰好经过 kk 条边到达 jj 的最短路。显然:

f[t][i][j]=f[t1][i][k]+G[k][j]f[t][i][j] = f[t - 1][i][k] + G[k][j]

另外,对于 ff 本身,也有:

f[t][i][j]=min1x<t{f[x][i][k]+f[tx][k][j]}f[t][i][j] = \min_{1 \le x < t}{f[x][i][k] + f[t - x][k][j] }

我们不妨把这一合并过程看作类似矩阵乘法的过程,那么就有:

f[t]=Gtf[t] = G^t

而每执行这样一次乘法的过程复杂度就高达 O(n3)\mathcal{O}(n^3),如果我们要朴素地预处理出 ff 的话复杂度便高达 O(kn3)\mathcal{O}(kn^3),显然是不可接受的。即使我们尝试用矩阵快速幂优化,那么单次查询复杂度便高达 O(n3logk)\mathcal{O}(n^3\log{k}),乘上 mm 后显然也是不可接受的。

于是我们只好求助…… 万能的分块(逃

我们可以取块长 L=10000=100L = \sqrt{10000} = 100。记 A=k100A = \lfloor \frac{k}{100} \rfloorB=kmod100B = k \mod 100

然后我们把每次询问的过程分成两步:

  • ss 出发恰好经过 LAL \cdot A 条边到达某个点 uu
  • uu 出发至少经过 BB 条边到达 tt

这样一来我们可以考虑开两个数组 fAf_AfBf_B。其中 fA[t][i][j]f_A[t][i][j] 表示从 iijj 恰好经过 LtL \cdot t 条边到达 jj 的最短路,而 fB[t][i][j]f_B[t][i][j] 则表示从 iijj 至少经过 tt 条边到达 jj 的最短路。那么对于每一次询问,其答案实际上就是:

ans=min{fA[A][s][u]+fB[B][u][t]}ans = \min { f_A[A][s][u] + f_B[B][u][t] }
只需要枚举 uu 就可以了,所以每一次询问我们可以在 O(n)\mathcal{O}(n) 的时间复杂度内解决。

接下来谈谈预处理。首先,fAf_A 可以通过如下方式得到:

fA[t]=(GL)tf_A[t] = (G{L})t

但是对于 fBf_B,由于它表示的是至少经过 tt 条边,我们还需要另跑一次 Floyd,得到最短路矩阵 dis[i][j]dis[i][j](表示从 iijj 的最短路),然后我们再把 GtG^tdis[i][j]dis[i][j] 按照之前说的方式合并,就得到了经过至少 tt 条边从 iijj 的最短路。

预处理复杂度就被压到了 O(n3k)\mathcal{O}(n^3\sqrt{k})。这样一来,总的复杂度就是 O(n3k+qn)\mathcal{O}(n^3\sqrt{k} + qn)

实现

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/08/07/hduoj-6331/