OI-wiki 图论进阶最小直径生成树MDST与图的绝对中心求解全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文以 OI-wiki 的 mdst 文档 为主体系统讲解最小直径生成树Minimum Diameter Spanning Tree, MDST的完整求解链路从树的直径这一前置概念出发引出图的绝对中心的定义与几何直观再到基于最短路距离数组与排序技巧的 $O(n^3 nm)$ 求解算法最后给出以绝对中心为根构造最短路径树从而还原 MDST 的完整 C 实现。读完本文你将掌握如何用多源最短路Floyd / Johnson预处理全源距离、如何利用 $\textit{rk}$ 排序数组在 $O(nm)$ 内枚举边上的绝对中心、以及如何在点中心与边中心两种情形下分别构造最小直径生成树并输出树边。前置知识树的直径最小直径生成树建立在直径概念之上。在阅读本文前建议先掌握 树的直径 的内容其核心结论是树上任意两节点之间最长的简单路径即为树的直径若树上所有边权均为正则树的所有直径中点重合。这一中点重合的性质正是后面推导图的绝对中心是最小直径生成树直径的中点这一关键结论的基础。直径的求解有两种 $O(n)$ 方法两次 DFS任意节点出发 DFS 到最远点 $z$再从 $z$ DFS 到最远点 $z$$\delta(z,z)$ 即为直径要求无负权边树形 DP记录每个点向下延伸的最长路径 $d_1$ 与次长路径 $d_2$$d_1d_2$ 的最大值即直径可处理负权边。而本文要处理的是一般无向图上的生成树问题直径的中点将推广为图的绝对中心。定义什么是最小直径生成树在无向图的所有生成树中直径最小的那一棵生成树就是最小直径生成树MDST。直观理解给定一张连通无向图我们要从中选出 $n-1$ 条边构成一棵树使得这棵树中任意两点间路径长度的最大值即直径最小。这并非最小生成树MST——MST 优化的是边权和而 MDST 优化的是树上最长路径。图的绝对中心求解最小直径生成树的第一步是找到图的绝对中心Absolute Center。定义图的绝对中心可以存在于一条边上也可以存在于某个结点上该中心到所有点的最短距离的最大值最小。即$$\min_{c \in \text{图}} \max_{i \in V} d(c, i)$$其中 $d(c,i)$ 表示中心点 $c$ 到结点 $i$ 的最短路径长度。根据定义可以直接推出一个重要事实到绝对中心距离最远的结点至少有两个。否则若最远结点唯一沿着指向它的方向微移中心即可减小最远距离矛盾于最大距离最小。数学建模令 $d(i,j)$ 为顶点 $i,j$ 间的最短路径长先通过多源最短路算法求出所有结点的最短路。定义 $\textit{rk}(i,j)$记录点 $i$ 到其他所有结点中第 $j$ 小的那个结点。换句话说$\textit{rk}(i)$ 是以 $i$ 为源点的所有结点按距离升序排列得到的序列$\textit{rk}(i,1)$ 到 $\textit{rk}(i,n)$ 依次对应距离 $i$ 最近到最远的结点。图的绝对中心可能在某条边上。枚举每一条边 $w(u,v)$并假设图的绝对中心 $c$ 就在这条边上。设中心 $c$ 距离 $u$ 的长度为 $x$$0 \le x \le w$则它距离 $v$ 的长度就是 $w - x$。对于图中的任意一点 $i$图的绝对中心 $c$ 到 $i$ 的距离为$$d(c,i) \min\big(d(u,i) x,\ d(v,i) (w - x)\big)$$即从 $c$ 出发到 $i$ 的最短路要么先走到 $u$ 再走 $d(u,i)$要么先走到 $v$ 再走 $d(v,i)$取两者较小值。下图展示了一个结点 $i$ 与绝对中心的位置关系结点 $i$ 既可能挂在 $u$ 一侧经 $u$ 到达也可能挂在 $v$ 一侧经 $v$ 到达。折线函数图像随着绝对中心 $c$ 在边 $w(u,v)$ 上滑动$x$ 从 0 变化到 $w$$d(c,i)$ 也随 $x$ 变化。注意到 $d(u,i)x$ 与 $d(v,i)(w-x)$ 是两条斜率互为相反数分别为 $1$ 与 $-1$的直线因此 $d(c,i)$ 作为二者的 $\min$其函数图像是一个由两条斜率相同的线段构成的折线段——先随 $x$ 增大而下降此时 $d(v,i)(w-x)$ 占优在两条直线交点处转向再随 $x$ 增大而上升此时 $d(u,i)x$ 占优。对于图上的任意一个结点都对应一条这样的折线。绝对中心到最远结点的距离函数写作$$f \max{ d(c,i) },\quad i \in [1,n]$$其函数图像是所有结点折线的上包络。这些折线交点中的最低点其横坐标就是图的绝对中心的位置。求解过程完整算法整个求解过程分为四步多源最短路预处理使用 Floyd 算法$O(n^3)$或 Johnson 全源最短路径算法稀疏图更优求出 $d$ 数组构建排序数组求出 $\textit{rk}(i,j)$对每个 $i$ 按距离升序排序检查结点上的绝对中心绝对中心可能恰好落在某个结点上用距离该结点最远的结点来更新答案。遍历所有结点 $$\textit{ans} \leftarrow \min\left(\textit{ans},\ d(i,\textit{rk}(i,n)) \times 2\right)$$ 注意此时直径候选值要乘以 2直径 中心到最远点的距离 × 2检查边上的绝对中心枚举所有边 $w(u,v)$从距离 $u$ 最远的结点开始扫描。用指针 $p$ 维护后缀最大值当出现 $$d\big(v,\textit{rk}(u,i)\big) \max_{ji1}^{n} d\big(v,\textit{rk}(u,j)\big)$$ 的情况时说明折线在此处发生了交点绝对值中心位置改变用下式更新 $$\textit{ans} \leftarrow \min\left(\textit{ans},\ d\big(u,\textit{rk}(u,i)\big) \max_{ji1}^{n} d\big(v,\textit{rk}(u,j)\big) w(u,v)\right)$$这里第四步的精髓在于对固定边 $(u,v)$按 $\textit{rk}(u)$ 的升序即 $d(u,\cdot)$ 递增枚举结点。上包络的最低点只会出现在$d(v,\textit{rk}(u,i))$ 大于其所有后继中最大值的位置——这正是两条折线相交、上包络产生向下的谷底的地方。利用单调扫描 后缀最大值单条边的检查可做到 $O(n)$总复杂度 $O(nm)$。核心代码bool cmp(int a, int b) { return val[a] val[b]; } void Floyd() { for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) d[i][j] min(d[i][j], d[i][k] d[k][j]); } void solve() { Floyd(); for (int i 1; i n; i) { for (int j 1; j n; j) { rk[i][j] j; val[j] d[i][j]; } sort(rk[i] 1, rk[i] 1 n, cmp); } int ans INF; // 图的绝对中心可能在结点上 for (int i 1; i n; i) ans min(ans, d[i][rk[i][n]] * 2); // 图的绝对中心可能在边上 for (int i 1; i m; i) { int u a[i].u, v a[i].v, w a[i].w; for (int p n, i n - 1; i 1; i--) { if (d[v][rk[u][i]] d[v][rk[u][p]]) { ans min(ans, d[u][rk[u][i]] d[v][rk[u][p]] w); p i; } } } }注意这段实现中结点中心与边中心两种情形得到的 $\textit{ans}$ 都是直径长度绝对中心到最远点距离的两倍由于边权可能为奇数最终输出直径时通常需要除以 2见下文完整实现。例题CodeForce 266D BerDonalds求无向带权图的最小直径本质就是求图的绝对中心到最远点距离的两倍是本节算法的直接应用。最小直径生成树从绝对中心构造原理绝对中心即直径中点根据图的绝对中心的定义容易得知图的绝对中心是最小直径生成树的直径的中点。这是因为绝对中心到所有点最远距离最小而树中任意两点路径必然经过直径中点于是以绝对中心为根生长出来的树其最长路径直径恰等于 $2 \times \max_i d(c,i)$这个值在绝对中心处取到全局最小。因此求解最小直径生成树需要两步找到图的绝对中心方法见上文以图的绝对中心为起点生成一棵最短路径树得到的即是最小直径生成树。所谓最短路径树SPT即以某点为根、满足根到每个结点的树上路径长度 该点到根的最短距离的生成树。构造方法对每条边 $(u,v,w)$若 $d(P,u)w d(P,v)$则边 $(u,v)$ 可被选入最短路径树。两种情形的处理绝对中心在结点 $P$ 上直接以 $P$ 为根构造最短路径树即可绝对中心在边 $(f_1,f_2)$ 上需要把中心物化为一个虚拟结点。具体做法是新增一个结点 $n1$ 表示中心向 $f_1$、$f_2$ 各连一条权为 $disu$、$disv$ 的边满足 $disudisvw$ 且 $disu \dfrac{d(u,\textit{rk}(u,i)) d(v,\textit{rk}(u,p)) w}{2} - d(u,\textit{rk}(u,i))$然后以虚拟结点为根构造最短路径树最后去掉虚拟结点及其两条边即可得到原图上的最小直径生成树。完整实现#include algorithm #include climits #include iostream #include vector using namespace std; constexpr int MAXN 502; using ll long long; using pii pairint, int; ll d[MAXN][MAXN], dd[MAXN][MAXN], rk[MAXN][MAXN], val[MAXN]; constexpr ll INF 1e17; int n, m; bool cmp(int a, int b) { return val[a] val[b]; } void floyd() { for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) d[i][j] min(d[i][j], d[i][k] d[k][j]); } struct node { ll u, v, w; } a[MAXN * (MAXN - 1) / 2]; void solve() { // 求图的绝对中心 floyd(); for (int i 1; i n; i) { for (int j 1; j n; j) { rk[i][j] j; val[j] d[i][j]; } sort(rk[i] 1, rk[i] 1 n, cmp); } ll P 0, ansP INF; // 绝对中心在点上 for (int i 1; i n; i) { if (d[i][rk[i][n]] * 2 ansP) { ansP d[i][rk[i][n]] * 2; P i; } } // 绝对中心在边上 int f1 0, f2 0; ll disu INT_MIN, disv INT_MIN, ansL INF; for (int i 1; i m; i) { ll u a[i].u, v a[i].v, w a[i].w; for (int p n, i n - 1; i 1; i--) { if (d[v][rk[u][i]] d[v][rk[u][p]]) { if (d[u][rk[u][i]] d[v][rk[u][p]] w ansL) { ansL d[u][rk[u][i]] d[v][rk[u][p]] w; f1 u, f2 v; disu (d[u][rk[u][i]] d[v][rk[u][p]] w) / 2 - d[u][rk[u][i]]; disv w - disu; } p i; } } } cout min(ansP, ansL) / 2 \n; // 最小路径生成树 vectorpii pp; for (int i 1; i 501; i) for (int j 1; j 501; j) dd[i][j] INF; for (int i 1; i 501; i) dd[i][i] 0; if (ansP ansL) { for (int j 1; j n; j) { for (int i 1; i m; i) { ll u a[i].u, v a[i].v, w a[i].w; if (dd[P][u] w d[P][v] dd[P][u] w dd[P][v]) { dd[P][v] dd[P][u] w; pp.push_back({u, v}); } u a[i].v, v a[i].u, w a[i].w; if (dd[P][u] w d[P][v] dd[P][u] w dd[P][v]) { dd[P][v] dd[P][u] w; pp.push_back({u, v}); } } } for (auto [x, y] : pp) cout x y \n; } else { d[n 1][f1] disu; d[f1][n 1] disu; d[n 1][f2] disv; d[f2][n 1] disv; a[m 1].u n 1, a[m 1].v f1, a[m 1].w disu; a[m 2].u n 1, a[m 2].v f2, a[m 2].w disv; n 1; m 2; floyd(); P n; for (int j 1; j n; j) { for (int i 1; i m; i) { ll u a[i].u, v a[i].v, w a[i].w; if (dd[P][u] w d[P][v] dd[P][u] w dd[P][v]) { dd[P][v] dd[P][u] w; pp.push_back({u, v}); } u a[i].v, v a[i].u, w a[i].w; if (dd[P][u] w d[P][v] dd[P][u] w dd[P][v]) { dd[P][v] dd[P][u] w; pp.push_back({u, v}); } } } cout f1 f2 \n; for (auto [x, y] : pp) if (x ! n y ! n) cout x y \n; } } void init() { for (int i 1; i 501; i) for (int j 1; j 501; j) d[i][j] INF; for (int i 1; i 501; i) d[i][i] 0; } int main() { init(); cin n m; for (int i 1; i m; i) { ll u, v, w; cin u v w; w * 2; // 边权乘 2避免除以 2 时的精度问题 d[u][v] w, d[v][u] w; a[i].u u, a[i].v v, a[i].w w; } solve(); return 0; }实现要点说明边权乘 2main中读入边权后立即w * 2此后所有距离均为偶数disu、直径等计算结果可直接整除避免浮点误差最终输出直径时再min(ansP, ansL) / 2还原排序键cmp依赖全局数组valval[j] d[i][j]需在每次排序前写入故rk[i]的排序逐行进行后缀最大值指针边中心扫描中p始终指向当前已扫描结点的后缀中 $d(v,\cdot)$ 最大的结点当d[v][rk[u][i]] d[v][rk[u][p]]时即出现交点更新答案并把p移动到i最短路径树判定dd[P][u] w d[P][v]判定边 $(u,v)$ 落在从 $P$ 出发的最短路径上即三角形等式成立dd[P][u] w dd[P][v]则保证每个点只被其最短路径上的前驱第一次更新时选中配合dd数组去重避免输出重复边虚拟结点边中心情形下以虚拟结点 $n1$ 为根建树后输出树边时需过滤掉包含虚拟结点的边x ! n y ! n并在输出前先输出真实边 $(f_1,f_2)$ 补全树的连通性。复杂度分析步骤复杂度多源最短路Floyd$O(n^3)$构造 $\textit{rk}$ 排序数组$n$ 次排序$O(n^2 \log n)$枚举结点上的绝对中心$O(n)$枚举边上的绝对中心$m$ 条边 × $O(n)$ 扫描$O(nm)$最短路径树构造$O(nm)$总复杂度$O(n^3 nm)$Johnson 预处理时稀疏图为 $O(nm\log n)$在 $n$ 较小如 $n \le 500$的稠密图上Floyd $O(nm)$ 扫描的整套流程可在 $O(n^3)$ 内完成这也是上述代码将MAXN设为 502 的适用场景。例题SPOJ MDST最小直径生成树的模板题直接应用上述算法timus 1569. Networking the Iset求给定网络的最小直径生成树实际为最小半径生成树问题与 MDST 思路相通SPOJ PT07C - The GbAaY Kingdom树上的最小直径生成树本质是求树的绝对中心即树的半径可用两次 DFS / 树形 DP 简化求解。总结最小直径生成树问题的求解可以浓缩为一条清晰的链路预处理全源最短路Floyd / Johnson按距离排序构建 $\textit{rk}$ 数组求图的绝对中心结点中心直接取 $\max_i d(i,j)$ 最小者边中心用折线上包络最低点的几何视角配合后缀最大值指针在 $O(nm)$ 内枚举以绝对中心为根构造最短路径树结点中心直接建树边中心通过虚拟结点物化中心后建树再还原。整个算法将生成树直径最小化这一全局优化问题转化为在边的连续区间上寻找函数包络最低点的几何问题再落到排序 单调扫描的工程实现上是图论中连续最优化离散化求解的经典范例。三张配套示意图位置关系图、单折线函数图、包络最低点图分别从结构与函数两个角度直观呈现了这一过程其原始 TikZ 源码可参考 mdst-graph.tex、mdst-plot1.tex 与 mdst-plot2.tex便于读者复现与改造图示。参考文献Play with Trees Solutions The GbAaY Kingdom【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考