2020-2021:teams:legal_string:jxm2001:基环树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:基环树 [2021/07/16 22:03] jxm2001 |
2020-2021:teams:legal_string:jxm2001:基环树 [2021/07/17 09:26] (当前版本) jxm2001 [例题四] |
||
|---|---|---|---|
| 行 278: | 行 278: | ||
| $$ | $$ | ||
| - | 考虑依次断开一条边，得到链后计算 $\max(d(u)+d(v)+\text{dis}(u,v))$，易知所有断边情况中的最小值就是直径的真实值。 | + | 考虑依次断开一条边，得到链后计算 $\max(d(u)+d(v)+\text{dis}(u,v))$ 得到生成树的直径，则所有断边情况中的最小值就是基环树的直径。 |
| + | |||
| + | 简短证明一下上述结论：首先任意断开一条环上的边可以得到一棵生成树，显然生成树的直径不小于基环树的直径。 | ||
| + | |||
| + | 事实上，取基环树直径的中点 $rt$，做 $rt$ 的最短路生成树，则最短路生成树的直径等于基环树的直径。证毕。 | ||
| 但这样时间复杂度是 $O(n^2)$，考虑优化。记环上的点分别为 $u_1,u_2\cdots u_m$，考虑先断开 $(u_1,u_m)$ 边，求出前缀 | 但这样时间复杂度是 $O(n^2)$，考虑优化。记环上的点分别为 $u_1,u_2\cdots u_m$，考虑先断开 $(u_1,u_m)$ 边，求出前缀 | ||
2020-2021/teams/legal_string/jxm2001/基环树.1626444219.txt.gz · 最后更改: 2021/07/16 22:03 由 jxm2001
