~ Esoteria Algorithm in Reverse Observatory

Cover Image

JZOJ3501 | 物语(ものがたり)

あぁ、青春の在り処も
幸福のルールも見つかってないから
泥に塗れたって
足が縺れたって
探しているんだろう
探していくんだろう

LGOJ P3393 | 逃离僵尸岛

Portal

​题目只有两个步骤:处理每个点的点权;跑一遍点权最短路。

​对于 KK 个城市,可以考虑把点权赋为 \infty 。对于 KK 个点周围的点,可以 bfs 进行预处理。但当 KK 较大时,复杂度为 O(kN)O(kN), 与队列优化的 Bellman ford 相同。

线段树优化 Dijkstra

过早的优化是万恶之源。
Go beyond speed.

一般的 Dijkstra 使用 priority_queue 维护当前最短路的距离,但不吸氧气的 STL 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。

负环与单源最短路计数

Prologue

  • 若图上存在一个环,环上各边的权值之和是负数,则称这个环是负环。

负环判定

​设 cnt[v] 表示从 11vv 的最短路径包含的边数,cnt[1]=0。当执行更新 d[v]=d[u]+w 时,同样更新 cnt[v]=cnt[u]+1。此时若发现 cnt[v]>=n,则图中有负环。若算法正常结束,则图中没有负环。

NOIAC52 | 计算机

Portal

计算机将重复上述过程,直到稳定

题中改写值的操作相当于最短路中对最短路长度的更新。每个节点上的值可以看作是从 1 号点到其它点的最短路的长度,而每个边的编号可以看作是该边的权。