矩阵乘法加速递推
昨晚参与AtCoder ABC 236时认为G题似乎可做,直到看到数据范围才发现事情没有那么简单。
由于最近学习离线数据结构,又见识过一道题意接近的题目,故想到整体二分,二分每一个节点第一次能恰好经过条边到达的时间,然后考虑DP求解。设计状态表示在该图上经过恰好次转移能否到达点。但很快发现每一次二分时均要重新在图上运行DP,时间复杂度无法承受。况且DP递推转移的次数高达,甚至不可能是线性的复杂度。
今天查看题解,发现有几个重要的,从未考虑过的trick:
- 既然要求能够经恰好次转移到达的最早的时间点,则我们将每条边的边权设为其加入图中的时间,则可以转化成恰有条边的最小瓶颈路。
- 发现很大,所以考虑通过矩阵乘法加速递推,也即所谓倍增优化DP的一种。