最小直径生成树
cpp
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> e(n, std::vector<int>(n, -1));
std::vector<std::vector<int64_t>> dis(n, std::vector<int64_t>(n, 1e18));
for (int i = 0; i < m; ++i) {
int u, v, l;
std::cin >> u >> v >> l;
l *= 2;
--u;
--v;
e[u][v] = e[v][u] = l;
dis[u][v] = dis[v][u] = l;
}
for (int i = 0; i < n; ++i)
dis[i][i] = 0;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
int64_t ans = 1e18;
int u0 = -1, v0 = -1, x0 = 0;
for (int u = 0; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
if (e[u][v] == -1)
continue;
int l = e[u][v];
std::vector<std::pair<int, int64_t>> p;
for (int i = 0; i < n; ++i) {
int64_t x = (dis[v][i] - dis[u][i] + l) / 2;
if (x < 0)
x = 0;
if (x > l)
x = l;
p.emplace_back(x, std::min(dis[u][i] + x, dis[v][i] + l - x));
}
std::sort(p.begin(), p.end());
std::vector<int> s;
for (int i = 0; i < n; ++i) {
if (!s.empty() && p[i].first + p[i].second <= p[s.back()].first + p[s.back()].second)
continue;
while (!s.empty() && p[i].first + p[i].second >= p[s.back()].first + p[s.back()].second && -p[i].first + p[i].second >= -p[s.back()].first + p[s.back()].second)
s.pop_back();
s.push_back(i);
}
if (p[s[0]].second - p[s[0]].first < ans) {
ans = p[s[0]].second - p[s[0]].first;
u0 = u;
v0 = v;
x0 = 0;
}
if (p[s.back()].second - l + p[s.back()].first < ans) {
ans = p[s.back()].second - l + p[s.back()].first;
u0 = u;
v0 = v;
x0 = l;
}
for (int i = 0; i + 1 < int(s.size()); ++i) {
int64_t res = (p[s[i]].second + p[s[i + 1]].second - p[s[i + 1]].first + p[s[i]].first) / 2;
if (res < ans) {
ans = res;
u0 = u;
v0 = v;
x0 = p[s[i]].first + p[s[i]].second - res;
}
}
}
}
std::cout << ans << "\n";// 直径
std::vector<int64_t> d(n, 1e18);
std::vector<int> vis(n), pre(n);
d[u0] = x0;
d[v0] = e[u0][v0] - x0;
pre[u0] = -1;
pre[v0] = u0;
for (int i = 0; i < n; ++i) {
int u = 0;
int64_t d0 = 1e18;
for (int v = 0; v < n; ++v) {
if (!vis[v] && d[v] < d0) {
u = v;
d0 = d[v];
}
}
if (pre[u] != -1)
std::cout << u + 1 << " " << pre[u] + 1 << "\n";// 方案
vis[u] = 1;
for (int v = 0; v < n; ++v) {
if (e[u][v] != -1 && d[v] > d[u] + e[u][v]) {
d[v] = d[u] + e[u][v];
pre[v] = u;
}
}
}
return 0;
}