势能

Johnson全源最短路：负权化正权，最后减去势能差 （1）建虚点0，add(0,i,0),跑st=0的单源最短路hi （2）e[i].w+=g[u]-h[v] ​ Q:为何这样不会得到错误答案？ ​ A：[ 最短路 - OI Wiki ]() （3）O(N^2*logN)跑n次dijk Code: ......

思路就是，将每一条 $w_{i,j}$ 改为 $w_{i,j} + h_i - h_j$，这样每一条从 $s \rightarrow t$ 被影响的值都是 $h_s - h_t$，所以修改图上的最短路等于原图的最短路。 然后这个构造显然就是一个差分约束系统，但这样的话复杂度不是就又回来了。 但我们可 ......

P4145 上帝造题的七分钟 2 / 花神游历各国 这道题解法很多，但我主要想提一下势能这个概念。 就像重力势能一样，一个物体只会往下落，且到达零势面之后不会再继续往下落（虽然和真实情况有出入） 因此，我们往往可以利用这个特性，来减少许多不必要的操作； 对于这道题而言，我们发现一个数如果已经开到1， ......

成功把这道小清新题做成了一道大数据结构题，我的评价是我是小丑。 首先显然要离散化对时间轴扫描线。这个除以 $2$ 下取整的操作显然启示我们往势能的方向思考，也就是我们希望能够找到某个变量，使得这个变量的均摊变化次数在可接受范围内。但是直接以每个元素的值为势能好像也不太对，因为一次全局除以 $2$ 之 ......