2.15

· · 个人记录

P2149 [SDOI2009] Elaxia的路线

4遍dij （一个点一遍）

x1存在dis[1]里 ，x2存在dis[2]里，y1存在dis[3]里,y2\to dis[4]

易证公共路径为一条链

如果dis_{1,x}+dis_{3,y}+w==dis_{1,y} 则x\to y在 x1到y1的最短路上

同理，可以得到x\to y在 x2到y2的最短路上，y\to x在 x2到y2的最短路上的情况

这样就得到了一个DAG

同向逆向分开跑最长链，取max

[GXOI/GZOI2019] 旅行者

按二进制位分组，第 i 位为1一组，0一组，对于每一组建超级源点

有向图，两遍

P2371 [国家集训队] 墨墨的等式

同于最短路，n 元跳楼机

P3403 跳楼机

Legacy

线段树优化建图

P4001 [ICPC-Beijing 2006] 狼抓兔子

最短路/网络流（最小割）

P3398 仓鼠找 sugar

找LCA

看二者的LCA是否在对方的路径上

P4281 [AHOI2008] 紧急集合 / 聚会

两两求lca找出深度最大的点，集合点在那里

然后再求路径长度

加强

$1\le m,n\le5\times10^5,1\le \sum k \le2\times 10^6

如果两两分组走，发现其中每条边恰好走两遍

答案即为 sun/2

[BJWC2010] 严格次小生成树

不断用非树边替换树边

Indecisive Taxi Fee