题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题，我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法：对于每只doge，我们都暴力地去建它连向它能跳到的点的边，边权为跳的次数。然后直接求一遍单元最短路即可。 很显然，这玩意的边的数量是$O(n^2)$的，求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的，但是我们会从中发现一个问题：既然一个doge的跳跃是多步的，那我们能否直接把几步拆开来，然后省略重复的边？ 例如： 优化为： 这样做看起来很星…

题面 蒟蒻博客：QAQ Solution 这是一道神题 首先，我们不妨想一下K=0，即求最短路方案数的部分分。 我们很容易可以想到一个做法，就是魔改迪杰斯特拉做法： 一个点可以更新到达其他点的距离，那个点的方案数就是这个点的方案数；如果一个点所更新出来的距离和之前的相等，那个点的方案数加等当前点的方案数。 用式子可以表现为： $$f[i]=f[i] (dis[j]>dis[i]+x)$$ $$f[j]+=f[i] (dis[j]==dis[i]+x)$$ (i表示当前点，j表示它更新的点，x为i到j那条路的距离) …

题面 传送门:洛咕 Solution 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到2的n次方，那么这两个点可以用1的时间相互到达。 也就是说，我们把距离能为2的n次方的点对用边权为1的边连上，再做一次最短路径，就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。 考虑使用DP。 我们设$f[i][j][k]$ 表示 $i$到$j$是否能以$2$的$k$次方的距离相互到达。 转移的时候得运…

题面 传送门:洛谷 Solution 这题的思想很巧妙. 首先,我们可以考虑一下最暴力的做法,对每个时刻的所有点都求一遍单元最短路 因为最多只有200个时刻,时间复杂度为$O(n^3log(n+m)))$ (堆优化的迪杰斯特拉) 显然对于$n=200$,并过不了 我们可有进一步分析 这一题,我们堆优化的迪杰斯特拉慢在每加入一个点,我们每一次都得对全图彻彻底底做一轮松弛 那换个角度考虑,如果我只松弛经过新加入的点的点对呢? 没错,就得用Floyd了. 因为Floyd本质就是一个DP,给了我们极大的魔改的空间 考虑到F…

题面 传送门:https://www.luogu.org/problemnew/show/P1462 Solution 这道题如果去除掉经过城市的收费.那么就是裸的最短路 但是题目要求经过城市中最多的一次性收费的最小值,也就是说让经过的最大值尽可能小 那我们可以考虑二分这个最大值 一切收费大于我们二分的值的城市统统不走 在最短路那里改一下就好了 然后就OjbK了 时间复杂度 $O(n*logn*logb)$ Code //Luogu P1462 通往奥格瑞玛的道路 //May,27th,2018 /…