图的绝对中心

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

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


设 $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

#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();
}
最后修改:2020 年 07 月 30 日 10 : 19 PM