最小直径生成树
在学习最小直径生成树(Minimum Diameter Spanning Tree)前建议先阅读 树的直径 的内容。
定义
在无向图的所有生成树中,直径最小的那一棵生成树就是最小直径生成树。
图的绝对中心
求解直径最小生成树,首先需要找到 图的绝对中心,图的绝对中心 可以存在于一条边上或某个结点上,该中心到所有点的最短距离的最大值最小。
根据 图的绝对中心 的定义可以知道,到绝对中心距离最远的结点至少有两个。
令 为顶点 间的最短路径长,通过多源最短路算法求出所有结点的最短路。
记录点 到其他所有结点中第 小的那个结点。
图的绝对中心可能在某条边上,枚举每一条边 ,并且假设图的绝对中心 就在这条边上。那么距离 的长度为 (),距离 的长度就是 。
对于图中的任意一点 ,图的绝对中心 到 的距离为 。
举例一个结点 ,该结点与图的绝对中心的位置关系如下图。
随着图的绝对中心 在边上的改变会生成一个距离与 位置的函数图像。显然的,当前的 的函数图像是一个两条斜率相同的线段构成的折线段。
对于图上的任意一结点,图的绝对中心到最远距离结点的函数就写作 ,其函数图像如下。
并且这些折线交点中的最低点,横坐标就是图的绝对中心的位置。
图的绝对中心可能在某个结点上,用距离预选结点最远的那个结点来更新,即 。
过程
-
使用多源最短路算法(Floyd,Johnson 等),求出 数组;
-
求出 ,并将其升序排序;
-
图的绝对中心可能在某个结点上,用距离预选结点最远的那个结点来更新,遍历所有结点并用 更新最小值。
-
图的绝对中心可能在某条边上,枚举所有的边。对于一条边 从距离 最远的结点开始更新。当出现 的情况时,用 来更新。因为这种情况会使图的绝对中心改变。
实现
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;
}
}
}
}
|
例题
最小直径生成树
根据图的绝对中心的定义,容易得知图的绝对中心是最小直径生成树的直径的中点。
求解最小直径生成树首先需要找到图的绝对中心。以图的绝对中心为起点,生成一个最短路径树,那么就可以得到最小直径生成树了。
实现
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128 | #include <bits/stdc++.h>
using namespace std;
const int MAXN = 502;
typedef long long ll;
typedef pair<int, int> pii;
ll d[MAXN][MAXN], dd[MAXN][MAXN], rk[MAXN][MAXN], val[MAXN];
const 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';
// 最小路径生成树
vector<pii> 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;
d[u][v] = w, d[v][u] = w;
a[i].u = u, a[i].v = v, a[i].w = w;
}
solve();
return 0;
}
|
例题
SPOJ MDST
timus 1569. Networking the "Iset"
SPOJ PT07C - The GbAaY Kingdom
参考文献
Play with Trees Solutions The GbAaY Kingdom
本页面最近更新:2023/12/12 22:35:43,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Alisahhh, billchenchina, Early0v0, Enter-tainer, iamtwz, Ir1d, ksyx, leoleoasd, Marcythm, mcendu, opsiff, ouuan, ShaoChenHeng, StudyingFather, Suiseiseki-2016, TrisolarisHD, wplf
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用