图的绝对中心

图的绝对中心

图的绝对中心指的是到图中所有结点最远距离最小的点。这个点可能是图中的某个结点或在某边上。

根据定义可以看出,到绝对中心距离最远的结点至少有两个。


设 $d[i][j]$ 为结点 $i$ 到结点 $j$ 的最短距离(预处理)。

考虑绝对中心 $center$ 在边 $(u,v)$ 上 ($u = v$ 时即为结点)。

那么结点 $i$ 到 $center$ 的距离函数图像即为:

那么对于所有结点到 $center$ 的距离函数图像即为:

可以发现,实线部分的最低点就是我们要求的绝对中心。因此我们只需要枚举所有边和点,然后计算相应答案的最小值即可。


接下来就是如何计算上图中的最低点了。

首先我们发现对于 $d[u][i] \leq d[u][j], d[v][i] \leq d[v][j]$,$i$ 点是不会对答案有贡献的,因此可以去掉。

将所有没有贡献的点去掉后,因为所有折线的斜率的绝对值相同,所以如果我们按照 $d[u][i]$ 进行从小到大排序的话,$d[v][i]$ 的值一定是递减的。然后我们就可以通过顺序枚举两折线交点找到答案。

总的时间复杂度为 $O(n^3 + n(m+n))$ 或 $O(nm\log n + n(m + n))$。区别在于预处理 $d[i][j]$ 的方式。

应用

最小直径生成树

只要求出图的绝对中心即可,最小直径即为到图的绝对中心的最远距离乘二。因为到绝对中心距离最远的结点至少有两个。

至于生成树只要记录一下绝对中心的位置,然后跑一个最短路树即可。

例题

spoj1479

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int INF = 0x3f3f3f3f;
int n, m;
int d[maxn][maxn], w[maxn][maxn];
int rk[maxn][maxn];
int ans, cu, cv;
double dis[maxn];

void floyd() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++) d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) rk[i][j] = j;
sort(rk[i] + 1, rk[i] + 1 + n,
[&](const int &a, const int &b) { return d[i][a] < d[i][b]; });
}
}

void solve(int u, int v) {
vector<pair<int, int>> tmp, vec;
for (int i = 1; i <= n; i++) tmp.push_back({d[u][rk[u][i]], d[v][rk[u][i]]});
for (int i = 0; i < tmp.size(); i++) {
while (!vec.empty() && vec.back().second <= tmp[i].second) vec.pop_back();
vec.push_back(tmp[i]);
}
int D = INF; // 直径
double a; // 绝对中心距离u点的偏移
if (vec.size() == 1) {
if (vec[0].first < vec[0].second) {
a = 0;
D = 2 * vec[0].first;
} else {
a = w[u][v];
D = 2 * vec[0].second;
}
} else {
for (int i = 1; i < vec.size(); i++) {
if (D > w[u][v] + vec[i - 1].first + vec[i].second) {
a = (w[u][v] + vec[i].second - vec[i - 1].first) / 2.0;
D = w[u][v] + vec[i - 1].first + vec[i].second;
}
}
}
if (D < ans) {
ans = D;
cu = u, cv = v;
dis[u] = a;
dis[v] = w[u][v] - a;
}
}

int path[maxn];

void dij() {
for (int i = 1; i <= n; i++)
if (i != cu && i != cv) dis[i] = 1e9;
priority_queue<pair<double, int>, vector<pair<double, int>>,
greater<pair<double, int>>>
pq;
pq.push({dis[cu], cu});
pq.push({dis[cv], cv});
path[cu] = path[cv] = -1;
while (!pq.empty()) {
auto it = pq.top();
pq.pop();
int u = it.second;
if (it.first > dis[u]) continue;
for (int v = 1; v <= n; v++) {
if (v != u && w[u][v] < INF && dis[u] + w[u][v] < dis[v]) {
dis[v] = dis[u] + w[u][v];
path[v] = u;
pq.push({dis[v], v});
}
}
}
if (cu != cv) {
if (cu > cv) swap(cu, cv);
printf("%d %d\n", cu, cv);
}
for (int i = 1; i <= n; i++) {
if (path[i] != -1) {
int u = i, v = path[i];
if (u > v) swap(u, v);
printf("%d %d\n", u, v);
}
}
}

int main() {
scanf("%d%d", &n, &m);
memset(d, 0x3f, sizeof(d));
memset(w, 0x3f, sizeof(w));
for (int i = 1; i <= n; i++) d[i][i] = 0, w[i][i] = 0;
for (int i = 0, u, v, x; i < m; i++) {
scanf("%d%d%d", &u, &v, &x);
d[u][v] = d[v][u] = min(d[u][v], x);
w[u][v] = w[v][u] = min(w[u][v], x);
}
floyd();
ans = INF;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
if (w[i][j] < INF) solve(i, j);
}
printf("%d\n", ans);
dij();
}