最小直径生成树
在学习最小直径生成树(Minimum Diameter Spanning Tree)前建议先阅读 树的直径 的内容。
在无向图的所有生成树中,直径最小的那一棵生成树就是最小直径生成树。
图的绝对中心¶
求解直径最小生成树,首先需要找到 图的绝对中心 , 图的绝对中心 可以存在于一条边上或某个结点上,该中心到所有点的最短距离的最大值最小。
根据 图的绝对中心 的定义可以知道,到绝对中心距离最远的结点至少有两个。
令 d[i][j]
为顶点
rk[i][j]
记录点
图的绝对中心可能在某条边上,枚举每一条边
对于图中的任意一点
举例一个结点
随着图的绝对中心
对于图上的任意一结点,图的绝对中心到最远距离结点的函数就写作
并且这些折线交点中的最低点,横坐标就是图的绝对中心的位置。
图的绝对中心可能在某个结点上,用距离预选结点最远的那个结点来更新,即
算法流程¶
-
求出
rk[i][j]
,并将其升序排序; -
图的绝对中心可能在某个结点上,用距离预选结点最远的那个结点来更新,遍历所有结点并用
\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,1)) \times 2) -
图的绝对中心可能在某条边上,枚举所有的边。对于一条边
w(u,j) u d(v,\textit{rk}(u,i)) > d(v,\textit{rk}(u,i-1)) \textit{ans}\leftarrow \min(\textit{ans}, d(v,\textit{rk}(u,i))+d(v,\textit{rk}(u,i-1))+w(i,j))
参考实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | 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;
}
}
}
}
|
例题¶
最小直径生成树¶
根据图的绝对中心的定义,容易得知图的绝对中心是最小直径生成树的直径的中点。
求解最小直径生成树首先需要找到图的绝对中心。以图的绝对中心为起点,生成一个最短路径树,那么就可以得到最小直径生成树了。
例题¶
timus 1569. Networking the "Iset"
SPOJ PT07C - The GbAaY Kingdom
参考文献¶
Play with Trees Solutions The GbAaY Kingdom
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用