标签：图论 LUOGU 短路 textbf DFN mathcal times

LUOGU_图论

ST表+DFN序LCA

每次在自己的DFN序位置放入自己的父亲

询问的时候l+1

ST表+欧拉序LCA

\(u,v\) 在欧拉序中的第一个位置之间的深度最小位置就是LCA

---

树的直径

相距最远的两个点

\(\max_{u,v}dis(u,v)=\max_{u,v}(dep_u+dep_v-2dep_{lca(u,v)})\)

边权非负：两次BFS

边权有负：DP

动态维护直径 P6845 Dynamic Diameter：

---

树的重心

重心最多有两个，无根树计数时如果需要钦定根，可以钦定重心。

---

最短路

单源最短路

一轮 Bellman-Ford 松弛可以看作一次 \(\{min,+\}\) 矩阵乘法：

\[\textbf{E}=\begin{Bmatrix}e_{1,1}&\cdots&e_{n,1}\\\vdots&\ddots&\vdots\\e_{1,n}&\cdots&e_{n,n}\end{Bmatrix} \]

\(\textbf{E}^{n-1}\times \vec d\) 则得到最终结果

P6190 魔法：\(\textbf{E}^{n-1}\times (K\times \textbf{E}^{n-1})^k\times\vec d\)

P1266 速度限制：分层图：图论中一个点表示的信息可以是很丰富的，当我们觉得一个点的信息单薄时，可以考虑像 dp 状态加维度一样给点也加一维信息。

P2149 Elaxia的路线：最短路径图，分为同向与异向，处理出同时在最短路上的边，在这上面找最长链即可。

差分约束：\(c_i\le c_j+x\)

P7624 地铁：二分环长上下界，并将环长 $\sum L_i+k\times mid $，将二分的环长与常数分离开，这样可以通过 \(k\) 的正负判断 \(k\) 应该增大还是减小，这样也可以辅助发现合法的答案一定是一个区间。

多源最短路：

全源最短路：

无负环：Dij\(\mathcal O(nm\log m)\)

有负环：Johnson \(\mathcal O(nm\log m)\)

好写+稠密图：Floyed \(\mathcal O(n^3)\)

---

连通性

P3825 游戏：首先可以枚举 \(x\) 是 \(a,b,c\) 的哪一个 \(\mathcal O(3^d(n+m))\) 跑 2-SAT。但 \(x\) 只需要选择 \(a,b\) 就可以覆盖 \(A,B,C\) 三种情况了，即不论选择 \(A,B,C\) 的哪一个， \(x=a,b\) 中总有一种情况可以统计到。

P5058 嗅探器：DFN序确定相对位置，其实就是求A，B之间的割点，这里以A为根，通过DFN序确定其在树上的相对位置。（告诉我们Tarjan并不只是一个黑盒算法）

弱联通

连通性删边：即删去一些边后连通性不变，在一些有特殊节点的图上，这样往往可以使得最后有用的边所剩无几。

P7737 [NOI2021] 庆典：先缩点，再删边，删成一个叶向树了。

---

欧拉回路

找欧拉回路通过DFS搜索，并加入当前弧优化。

标签：图论,LUOGU,短路,textbf,DFN,mathcal,times
From： https://www.cnblogs.com/lupengheyyds/p/18517394