2025 vertigo - 图论选讲 - pb

*表示没写 / 懒得写。还有些非常蠢的题删掉了。

[0] [PA 2025] 瞬间传送

不知道为什么在这题卡了很久，实际上不难。注意此题是双向边，所以如果连接了 $x,y$，那么对于 $u,v$ 两点，新的路径有 $u\rightarrow x\rightarrow y\rightarrow v$ 和 $u\rightarrow y\rightarrow x\rightarrow v$ 两种。枚举答案 $r$，每次提出所有 $dis_{u,v}=r+1$ 的所有点对，判断加每个边合不合法，暴力是 $\mathcal O(n^4)$ 的（可以用 bitset 除个 $\omega$），瓶颈在于连一条边有两种走法，只有两种都不行新加的边才不合法。观察到如果 $dis_{u,x}\le dis_{u,y}$，那么新增路径一定是 $u\rightarrow x\rightarrow y\rightarrow v$，另一个不优。所以预处理 $f_{u,y}$ 表示对于所有不合法的 $(u,v)$，$dis_{v,y}$ 的最大值。每次 $f$ 更新的时候，暴力枚举 $x$ 判定，均摊是 $\mathcal O(n^3)$ 的。

CF1656I Neighbour Ordering

QOJ6807 Travel Dream

xmascon22_h Happy Game

QOJ7177 Many Many Cycles

QOJ4805 Grammy Sorting
[PA 2020] Trzy drogi

QOJ9844 Marriage II

CF1284G Seollal

QOJ895 Color

ARC122F Domination