题目归纳

· · 个人记录

倍增专题

幸福路径(倍增floyed板子题)

思路整理：看见数据范围 n<=100，m<=1000,立马反应过来该题可能适用floyed，spfa 或者其他奇奇怪怪的图论板子。

如果是spfa，很有可能被卡成狗 这年头谁不卡spfa，而且分析题意可得，有环，还有自环，如果出题人稍稍把ρ调大一点，很有可能在spfa过程中分裂出很多子路径，空间和时间都消受不起，预计分数10~30pts.

很明显，这得请出我们的floyed同志了，但是floyed的松弛方程得改一改，变成

f[i][j][k] = f[i][t][k - 1] + f[t][j][1] * p

到目前为止，大体的思路已经出来了，就是利用floyed不断更新。

题目里又说了保留一位小数，其实已经在暗示我们精度问题，只要我们大致计算得差不多就行了，也就是说，只要我们循环的次数足够多，就能得到一个近似值。

但是，计算一下复杂度，发现floyed已经需要O(n^3)复杂度了，如果ρ再来个类似于0.999999……这样的小数，很容易就卡掉了。

所以我们需要优化，floyed无法优化，只能将外面一层ρ进行O(1)或者O(logn)级的优化，发现我们在求的无非是在p^k情况下的floyed，考虑类似于快速幂的算法。

快速幂无非就是二进制拆分，故我们可以将第三维 p^k 拆分 成 p^k - 1 * p ^ k - 1的形式，故方程就转换为

f[i][j][k] = f[i][t][k - 1] * f[t][j][k - 1] * p ^ k - 1;

所以外层就变成近似于常数的复杂度，预计复杂度为 O(30 * n ^ 3)

细节:

1.在求p^k的时候，不要拿p^k > 0.01这种作为边界，很容易导致精度出错，尽量多循环。

2.注意是有向图。

3.记得初始化成-INF