跳转至

最小直徑生成樹

在學習最小直徑生成樹（Minimum Diameter Spanning Tree）前建議先閲讀 樹的直徑 的內容。

定義

在無向圖的所有生成樹中，直徑最小的那一棵生成樹就是最小直徑生成樹。

圖的絕對中心

求解直徑最小生成樹，首先需要找到 圖的絕對中心，圖的絕對中心 可以存在於一條邊上或某個結點上，該中心到所有點的最短距離的最大值最小。

根據 圖的絕對中心 的定義可以知道，到絕對中心距離最遠的結點至少有兩個。

令 \(d(i,j)\) 為頂點 \(i,j\) 間的最短路徑長，通過多源最短路算法求出所有結點的最短路。

\(\textit{rk}(i,j)\) 記錄點 \(i\) 到其他所有結點中第 \(j\) 小的那個結點。

圖的絕對中心可能在某條邊上，枚舉每一條邊 \(w=(u,v)\)，並且假設圖的絕對中心 \(c\) 就在這條邊上。那麼距離 \(u\) 的長度為 \(x\)（\(x \leq w\)），距離 \(v\) 的長度就是 \(w - x\)。

對於圖中的任意一點 \(i\)，圖的絕對中心 \(c\) 到 \(i\) 的距離為 \(d(c,i)=\min(d(u,i) + x, d(v,i) + (w - x))\)。

舉例一個結點 \(i\)，該結點與圖的絕對中心的位置關係如下圖。

mdst1

隨着圖的絕對中心 \(c\) 在邊上的改變會生成一個距離與 \(c\) 位置的函數圖像。顯然的，當前的 \(d(c,i)\) 的函數圖像是一個兩條斜率相同的線段構成的折線段。

mdst2

對於圖上的任意一結點，圖的絕對中心到最遠距離結點的函數就寫作 \(f = \max\{ d(c,i)\},i \in[1,n]\)，其函數圖像如下。

mdst3

並且這些折線交點中的最低點，橫座標就是圖的絕對中心的位置。

圖的絕對中心可能在某個結點上，用距離預選結點最遠的那個結點來更新，即 \(\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,n))\times 2)\)。

過程

  1. 使用多源最短路算法（Floyd，Johnson 等），求出 \(d\) 數組；

  2. 求出 \(\textit{rk}(i,j)\)，並將其升序排序；

  3. 圖的絕對中心可能在某個結點上，用距離預選結點最遠的那個結點來更新，遍歷所有結點並用 \(\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,n)) \times 2)\) 更新最小值。

  4. 圖的絕對中心可能在某條邊上，枚舉所有的邊。對於一條邊 \(w(u,v)\) 從距離 \(u\) 最遠的結點開始更新。當出現 \(d(v,\textit{rk}(u,i)) > \max_{j=i+1}^n d(v,\textit{rk}(u,j))\) 的情況時，用 \(\textit{ans}\leftarrow \min(\textit{ans}, d(u,\textit{rk}(u,i))+\max_{j=i+1}^n d(v,\textit{rk}(u,j))+w(u,v))\) 來更新。因為這種情況會使圖的絕對中心改變。

實現 
 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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用