minimum_diameter_spanning_tree.hpp¶
在连通、非负边权无向图中求直径最小的生成树，并返回原边编号；复用 Dijkstra 出队顺序寻找绝对中心，树输入直接线性处理。
Complexity: Time: \(O(V (V + E) \log (V + E + 1) + VE)\); \(O(V + E)\) for tree input. Space: \(O(V^{2} + E)\); \(O(V + E)\) including recursion for tree input.
AC 记录：minimum_diameter_spanning_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V(V+E) log(V+E+1) + VE); O(V+E) for tree input.
/// Space: O(V^2+E); O(V+E) including recursion for tree input.
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct minimum_diameter_spanning_tree_result {
Weight dia{};
std::vector<int> eid;
};
/// @brief Minimum-diameter spanning tree of a connected undirected graph.
/// Weights are nonnegative; finite shortest distances and the answer must be
/// below numeric_limits<Weight>::max(). Parallel edges and loops are allowed.
/// An absolute center lies at a vertex or within an edge. All-pairs shortest
/// paths and an endpoint-distance sweep locate it; a shortest-path tree from
/// that center realizes the optimum. Equal optima need not use the same edges.
template <class Weight>
minimum_diameter_spanning_tree_result<Weight> minimum_diameter_spanning_tree(
int n, const std::vector<std::tuple<int, int, Weight>> &es) {
assert(n > 0);
struct adjacent_edge { int to; Weight w; int id; };
std::vector<std::vector<adjacent_edge>> g(n);
int m = 0;
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v, w] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n && w >= Weight{});
if (u == v) continue;
g[u].push_back({v, w, id});
g[v].push_back({u, w, id});
++m;
}
minimum_diameter_spanning_tree_result<Weight> res;
res.eid.reserve(n - 1);
if (m == n - 1) {
auto dfs = [&](auto &&self, int u, int parent) -> Weight {
Weight best{};
for (auto [v, w, id] : g[u]) if (v != parent) {
Weight height = self(self, v, u) + w;
res.dia = std::max(res.dia, best + height);
best = std::max(best, height);
res.eid.push_back(id);
}
return best;
};
dfs(dfs, 0, -1);
return res;
}
const Weight inf = std::numeric_limits<Weight>::max();
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
std::vector<int> pe(n, -1);
// Caller initializes distances and seeds q; the drained heap retains space.
auto sp = [&](std::vector<Weight> &d) {
std::vector<int> order;
order.reserve(n);
while (!q.empty()) {
auto [distance, u] = q.top();
q.pop();
if (distance != d[u]) continue;
order.push_back(u);
for (auto [v, w, id] : g[u]) {
// Check before adding, so irrelevant long detours cannot overflow.
if (w < d[v] && distance < d[v] - w) {
d[v] = distance + w;
pe[v] = id;
q.emplace(d[v], v);
}
}
}
return order;
};
std::vector<std::vector<Weight>> dis(n);
std::vector<std::vector<int>> ord(n);
Weight best = inf;
int root = 0, center = -1;
Weight du{}, dv{};
for (int u = 0; u < n; ++u) {
dis[u].assign(n, inf);
dis[u][u] = Weight{};
q.emplace(Weight{}, u);
ord[u] = sp(dis[u]);
assert(int(ord[u].size()) == n); // Connected, representable distances.
std::reverse(ord[u].begin(), ord[u].end());
Weight radius = dis[u][ord[u][0]];
if (radius == Weight{}) {
for (int v = 0; v < n; ++v) if (v != u) res.eid.push_back(pe[v]);
return res;
}
if (radius < best && radius < best - radius) {
best = radius + radius;
root = u;
}
}
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v, w] = es[id];
// A longer-than-shortest edge can be replaced by its shorter endpoint path.
if (u == v || w >= best || w > dis[u][v]) continue;
Weight far = dis[v][ord[u][0]];
for (int x : ord[u]) if (dis[v][x] > far) {
Weight a = dis[u][x];
// The candidate diameter is a+far+w. Only form an improving sum.
if (a < best && far < best - a && w < best - a - far) {
best = a + far + w;
center = id;
// Integral weights give half-integral offsets with the same fraction.
// Dropping that common fraction preserves all shortest-path choices.
du = best / Weight(2) - a;
dv = best / Weight(2) - far;
}
far = dis[v][x];
}
}
assert(best < inf); // The returned diameter must fit below the sentinel.
std::vector<Weight> d(n, inf);
int other = -1;
if (center >= 0) {
auto [u, v, w] = es[center];
root = u;
other = v;
d[u] = du;
d[v] = dv;
q.emplace(du, u);
q.emplace(dv, v);
} else {
d[root] = Weight{};
q.emplace(Weight{}, root);
}
sp(d);
for (int u = 0; u < n; ++u) if (u != root && u != other) {
assert(pe[u] >= 0);
res.eid.push_back(pe[u]);
}
if (center >= 0) res.eid.push_back(center);
res.dia = best;
return res;
}
} // namespace noya
// NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
#ifndef NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
#define NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP 1
/// @complexity Time: O(V(V+E) log(V+E+1) + VE); O(V+E) for tree input.
/// Space: O(V^2+E); O(V+E) including recursion for tree input.
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct minimum_diameter_spanning_tree_result {
Weight dia{};
std::vector<int> eid;
};
/// @brief Minimum-diameter spanning tree of a connected undirected graph.
/// Weights are nonnegative; finite shortest distances and the answer must be
/// below numeric_limits<Weight>::max(). Parallel edges and loops are allowed.
/// An absolute center lies at a vertex or within an edge. All-pairs shortest
/// paths and an endpoint-distance sweep locate it; a shortest-path tree from
/// that center realizes the optimum. Equal optima need not use the same edges.
template <class Weight>
minimum_diameter_spanning_tree_result<Weight> minimum_diameter_spanning_tree(
int n, const std::vector<std::tuple<int, int, Weight>> &es) {
assert(n > 0);
struct adjacent_edge { int to; Weight w; int id; };
std::vector<std::vector<adjacent_edge>> g(n);
int m = 0;
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v, w] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n && w >= Weight{});
if (u == v) continue;
g[u].push_back({v, w, id});
g[v].push_back({u, w, id});
++m;
}
minimum_diameter_spanning_tree_result<Weight> res;
res.eid.reserve(n - 1);
if (m == n - 1) {
auto dfs = [&](auto &&self, int u, int parent) -> Weight {
Weight best{};
for (auto [v, w, id] : g[u]) if (v != parent) {
Weight height = self(self, v, u) + w;
res.dia = std::max(res.dia, best + height);
best = std::max(best, height);
res.eid.push_back(id);
}
return best;
};
dfs(dfs, 0, -1);
return res;
}
const Weight inf = std::numeric_limits<Weight>::max();
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
std::vector<int> pe(n, -1);
// Caller initializes distances and seeds q; the drained heap retains space.
auto sp = [&](std::vector<Weight> &d) {
std::vector<int> order;
order.reserve(n);
while (!q.empty()) {
auto [distance, u] = q.top();
q.pop();
if (distance != d[u]) continue;
order.push_back(u);
for (auto [v, w, id] : g[u]) {
// Check before adding, so irrelevant long detours cannot overflow.
if (w < d[v] && distance < d[v] - w) {
d[v] = distance + w;
pe[v] = id;
q.emplace(d[v], v);
}
}
}
return order;
};
std::vector<std::vector<Weight>> dis(n);
std::vector<std::vector<int>> ord(n);
Weight best = inf;
int root = 0, center = -1;
Weight du{}, dv{};
for (int u = 0; u < n; ++u) {
dis[u].assign(n, inf);
dis[u][u] = Weight{};
q.emplace(Weight{}, u);
ord[u] = sp(dis[u]);
assert(int(ord[u].size()) == n); // Connected, representable distances.
std::reverse(ord[u].begin(), ord[u].end());
Weight radius = dis[u][ord[u][0]];
if (radius == Weight{}) {
for (int v = 0; v < n; ++v) if (v != u) res.eid.push_back(pe[v]);
return res;
}
if (radius < best && radius < best - radius) {
best = radius + radius;
root = u;
}
}
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v, w] = es[id];
// A longer-than-shortest edge can be replaced by its shorter endpoint path.
if (u == v || w >= best || w > dis[u][v]) continue;
Weight far = dis[v][ord[u][0]];
for (int x : ord[u]) if (dis[v][x] > far) {
Weight a = dis[u][x];
// The candidate diameter is a+far+w. Only form an improving sum.
if (a < best && far < best - a && w < best - a - far) {
best = a + far + w;
center = id;
// Integral weights give half-integral offsets with the same fraction.
// Dropping that common fraction preserves all shortest-path choices.
du = best / Weight(2) - a;
dv = best / Weight(2) - far;
}
far = dis[v][x];
}
}
assert(best < inf); // The returned diameter must fit below the sentinel.
std::vector<Weight> d(n, inf);
int other = -1;
if (center >= 0) {
auto [u, v, w] = es[center];
root = u;
other = v;
d[u] = du;
d[v] = dv;
q.emplace(du, u);
q.emplace(dv, v);
} else {
d[root] = Weight{};
q.emplace(Weight{}, root);
}
sp(d);
for (int u = 0; u < n; ++u) if (u != root && u != other) {
assert(pe[u] >= 0);
res.eid.push_back(pe[u]);
}
if (center >= 0) res.eid.push_back(center);
res.dia = best;
return res;
}
} // namespace noya
#endif // NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
/// @complexity Time: O(V(V+E) log(V+E+1) + VE); O(V+E) for tree input.
/// Space: O(V^2+E); O(V+E) including recursion for tree input.
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct minimum_diameter_spanning_tree_result {
Weight dia{};
std::vector<int> eid;
};
/// @brief Minimum-diameter spanning tree of a connected undirected graph.
/// Weights are nonnegative; finite shortest distances and the answer must be
/// below numeric_limits<Weight>::max(). Parallel edges and loops are allowed.
/// An absolute center lies at a vertex or within an edge. All-pairs shortest
/// paths and an endpoint-distance sweep locate it; a shortest-path tree from
/// that center realizes the optimum. Equal optima need not use the same edges.
template <class Weight>
minimum_diameter_spanning_tree_result<Weight> minimum_diameter_spanning_tree(
int n, const std::vector<std::tuple<int, int, Weight>> &es) {
assert(n > 0);
struct adjacent_edge { int to; Weight w; int id; };
std::vector<std::vector<adjacent_edge>> g(n);
int m = 0;
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v, w] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n && w >= Weight{});
if (u == v) continue;
g[u].push_back({v, w, id});
g[v].push_back({u, w, id});
++m;
}
minimum_diameter_spanning_tree_result<Weight> res;
res.eid.reserve(n - 1);
if (m == n - 1) {
auto dfs = [&](auto &&self, int u, int parent) -> Weight {
Weight best{};
for (auto [v, w, id] : g[u]) if (v != parent) {
Weight height = self(self, v, u) + w;
res.dia = std::max(res.dia, best + height);
best = std::max(best, height);
res.eid.push_back(id);
}
return best;
};
dfs(dfs, 0, -1);
return res;
}
const Weight inf = std::numeric_limits<Weight>::max();
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
std::vector<int> pe(n, -1);
// Caller initializes distances and seeds q; the drained heap retains space.
auto sp = [&](std::vector<Weight> &d) {
std::vector<int> order;
order.reserve(n);
while (!q.empty()) {
auto [distance, u] = q.top();
q.pop();
if (distance != d[u]) continue;
order.push_back(u);
for (auto [v, w, id] : g[u]) {
// Check before adding, so irrelevant long detours cannot overflow.
if (w < d[v] && distance < d[v] - w) {
d[v] = distance + w;
pe[v] = id;
q.emplace(d[v], v);
}
}
}
return order;
};
std::vector<std::vector<Weight>> dis(n);
std::vector<std::vector<int>> ord(n);
Weight best = inf;
int root = 0, center = -1;
Weight du{}, dv{};
for (int u = 0; u < n; ++u) {
dis[u].assign(n, inf);
dis[u][u] = Weight{};
q.emplace(Weight{}, u);
ord[u] = sp(dis[u]);
assert(int(ord[u].size()) == n); // Connected, representable distances.
std::reverse(ord[u].begin(), ord[u].end());
Weight radius = dis[u][ord[u][0]];
if (radius == Weight{}) {
for (int v = 0; v < n; ++v) if (v != u) res.eid.push_back(pe[v]);
return res;
}
if (radius < best && radius < best - radius) {
best = radius + radius;
root = u;
}
}
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v, w] = es[id];
// A longer-than-shortest edge can be replaced by its shorter endpoint path.
if (u == v || w >= best || w > dis[u][v]) continue;
Weight far = dis[v][ord[u][0]];
for (int x : ord[u]) if (dis[v][x] > far) {
Weight a = dis[u][x];
// The candidate diameter is a+far+w. Only form an improving sum.
if (a < best && far < best - a && w < best - a - far) {
best = a + far + w;
center = id;
// Integral weights give half-integral offsets with the same fraction.
// Dropping that common fraction preserves all shortest-path choices.
du = best / Weight(2) - a;
dv = best / Weight(2) - far;
}
far = dis[v][x];
}
}
assert(best < inf); // The returned diameter must fit below the sentinel.
std::vector<Weight> d(n, inf);
int other = -1;
if (center >= 0) {
auto [u, v, w] = es[center];
root = u;
other = v;
d[u] = du;
d[v] = dv;
q.emplace(du, u);
q.emplace(dv, v);
} else {
d[root] = Weight{};
q.emplace(Weight{}, root);
}
sp(d);
for (int u = 0; u < n; ++u) if (u != root && u != other) {
assert(pe[u] >= 0);
res.eid.push_back(pe[u]);
}
if (center >= 0) res.eid.push_back(center);
res.dia = best;
return res;
}
} // namespace noya
// NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP