minimum_diameter_spanning_tree.hpp¶
在带权无向图中求直径最小的生成树，并构造对应树边。
Complexity: Time: O(V(E + V) log V + VE + V^2 log V). Space: O(V^2 + V + E).
AC 记录：minimum_diameter_spanning_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V(E + V) log V + VE + V^2 log V).
/// Space: O(V^2 + V + E).
#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 Construct a minimum-diameter spanning tree of a connected graph.
/// The center of an optimal tree can be placed at a vertex or inside one
/// graph edge. All-pairs shortest paths give every vertex eccentricity. For
/// an edge center, sorting vertices by distance from one endpoint makes the
/// maximum of the two endpoint-distance envelopes change monotonically, so
/// one sweep tests its best split point. Doubling edge weights keeps every
/// half-integral center exact. Finally, a shortest-path tree rooted at the
/// best absolute center realizes the selected minimum diameter.
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);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(w >= Weight{});
w *= Weight(2);
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
const Weight inf = std::numeric_limits<Weight>::max() / 4;
struct shortest_path_result {
std::vector<Weight> dis;
std::vector<int> pre;
std::vector<int> pe;
};
auto sp = [&](int s, const std::vector<std::vector<adjacent_edge>> &G) {
int siz = int(G.size());
shortest_path_result res{std::vector<Weight>(siz, inf),
std::vector<int>(siz, -1),
std::vector<int>(siz, -1)};
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
res.dis[s] = Weight{};
q.emplace(Weight{}, s);
while (!q.empty()) {
auto [dis, u] = q.top();
q.pop();
if (dis != res.dis[u]) {
continue;
}
for (auto [to, w, id] : G[u]) {
Weight can = dis + w;
if (can < res.dis[to]) {
res.dis[to] = can;
res.pre[to] = u;
res.pe[to] = id;
q.emplace(can, to);
}
}
}
return res;
};
std::vector<std::vector<Weight>> dis(n, std::vector<Weight>(n));
for (int s = 0; s < n; s++) {
dis[s] = sp(s, g).dis;
for (Weight val : dis[s]) {
assert(val != inf);
}
}
std::vector<std::vector<int>> ord(n, std::vector<int>(n));
Weight bvs = inf;
int bv = 0;
for (int u = 0; u < n; u++) {
for (int rhs = 0; rhs < n; rhs++) {
ord[u][rhs] = rhs;
}
std::stable_sort(ord[u].begin(), ord[u].end(),
[&](int a, int b) { return dis[u][a] > dis[u][b]; });
Weight va1 = dis[u][ord[u][0]] * Weight(2);
if (va1 < bvs) {
bvs = va1;
bv = u;
}
}
Weight bes = inf;
int be = -1;
int bu = -1;
int bw = -1;
Weight du{};
Weight dv{};
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w0] = es[id];
if (a == b) {
continue;
}
Weight w = w0 * Weight(2);
int prv = ord[a][0];
for (int u : ord[a]) {
if (dis[b][u] > dis[b][prv]) {
Weight va1 = dis[b][prv] + dis[a][u] + w;
if (va1 < bes) {
bes = va1;
be = id;
bu = a;
bw = b;
du = va1 / Weight(2) - dis[a][u];
dv = w - du;
}
prv = u;
}
}
}
minimum_diameter_spanning_tree_result<Weight> res;
if (bes < bvs) {
int o = n;
auto aug = g;
aug.emplace_back();
aug[o].push_back({bu, du, -1});
aug[o].push_back({bw, dv, -1});
auto tr = sp(o, aug);
res.dia = bes / Weight(2);
res.eid.reserve(n - 1);
for (int u = 0; u < n; u++) {
if (u != bu && u != bw) {
assert(tr.pe[u] >= 0);
res.eid.push_back(tr.pe[u]);
}
}
res.eid.push_back(be);
} else {
auto tr = sp(bv, g);
res.dia = bvs / Weight(2);
res.eid.reserve(n - 1);
for (int u = 0; u < n; u++) {
if (u != bv) {
assert(tr.pe[u] >= 0);
res.eid.push_back(tr.pe[u]);
}
}
}
return res;
}
} // namespace noya
#ifndef NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
#define NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP 1
/// @complexity Time: O(V(E + V) log V + VE + V^2 log V).
/// Space: O(V^2 + V + E).
#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 Construct a minimum-diameter spanning tree of a connected graph.
/// The center of an optimal tree can be placed at a vertex or inside one
/// graph edge. All-pairs shortest paths give every vertex eccentricity. For
/// an edge center, sorting vertices by distance from one endpoint makes the
/// maximum of the two endpoint-distance envelopes change monotonically, so
/// one sweep tests its best split point. Doubling edge weights keeps every
/// half-integral center exact. Finally, a shortest-path tree rooted at the
/// best absolute center realizes the selected minimum diameter.
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);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(w >= Weight{});
w *= Weight(2);
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
const Weight inf = std::numeric_limits<Weight>::max() / 4;
struct shortest_path_result {
std::vector<Weight> dis;
std::vector<int> pre;
std::vector<int> pe;
};
auto sp = [&](int s, const std::vector<std::vector<adjacent_edge>> &G) {
int siz = int(G.size());
shortest_path_result res{std::vector<Weight>(siz, inf),
std::vector<int>(siz, -1),
std::vector<int>(siz, -1)};
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
res.dis[s] = Weight{};
q.emplace(Weight{}, s);
while (!q.empty()) {
auto [dis, u] = q.top();
q.pop();
if (dis != res.dis[u]) {
continue;
}
for (auto [to, w, id] : G[u]) {
Weight can = dis + w;
if (can < res.dis[to]) {
res.dis[to] = can;
res.pre[to] = u;
res.pe[to] = id;
q.emplace(can, to);
}
}
}
return res;
};
std::vector<std::vector<Weight>> dis(n, std::vector<Weight>(n));
for (int s = 0; s < n; s++) {
dis[s] = sp(s, g).dis;
for (Weight val : dis[s]) {
assert(val != inf);
}
}
std::vector<std::vector<int>> ord(n, std::vector<int>(n));
Weight bvs = inf;
int bv = 0;
for (int u = 0; u < n; u++) {
for (int rhs = 0; rhs < n; rhs++) {
ord[u][rhs] = rhs;
}
std::stable_sort(ord[u].begin(), ord[u].end(),
[&](int a, int b) { return dis[u][a] > dis[u][b]; });
Weight va1 = dis[u][ord[u][0]] * Weight(2);
if (va1 < bvs) {
bvs = va1;
bv = u;
}
}
Weight bes = inf;
int be = -1;
int bu = -1;
int bw = -1;
Weight du{};
Weight dv{};
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w0] = es[id];
if (a == b) {
continue;
}
Weight w = w0 * Weight(2);
int prv = ord[a][0];
for (int u : ord[a]) {
if (dis[b][u] > dis[b][prv]) {
Weight va1 = dis[b][prv] + dis[a][u] + w;
if (va1 < bes) {
bes = va1;
be = id;
bu = a;
bw = b;
du = va1 / Weight(2) - dis[a][u];
dv = w - du;
}
prv = u;
}
}
}
minimum_diameter_spanning_tree_result<Weight> res;
if (bes < bvs) {
int o = n;
auto aug = g;
aug.emplace_back();
aug[o].push_back({bu, du, -1});
aug[o].push_back({bw, dv, -1});
auto tr = sp(o, aug);
res.dia = bes / Weight(2);
res.eid.reserve(n - 1);
for (int u = 0; u < n; u++) {
if (u != bu && u != bw) {
assert(tr.pe[u] >= 0);
res.eid.push_back(tr.pe[u]);
}
}
res.eid.push_back(be);
} else {
auto tr = sp(bv, g);
res.dia = bvs / Weight(2);
res.eid.reserve(n - 1);
for (int u = 0; u < n; u++) {
if (u != bv) {
assert(tr.pe[u] >= 0);
res.eid.push_back(tr.pe[u]);
}
}
}
return res;
}
} // namespace noya
#endif // NOYA_MINIMUM_DIAMETER_SPANNING_TREE_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O(V(E + V) log V + VE + V^2 log V).
/// Space: O(V^2 + V + E).
namespace noya {
template <class Weight> struct minimum_diameter_spanning_tree_result {
Weight dia{};
std::vector<int> eid;
};
/// @brief Construct a minimum-diameter spanning tree of a connected graph.
/// The center of an optimal tree can be placed at a vertex or inside one
/// graph edge. All-pairs shortest paths give every vertex eccentricity. For
/// an edge center, sorting vertices by distance from one endpoint makes the
/// maximum of the two endpoint-distance envelopes change monotonically, so
/// one sweep tests its best split point. Doubling edge weights keeps every
/// half-integral center exact. Finally, a shortest-path tree rooted at the
/// best absolute center realizes the selected minimum diameter.
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);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(w >= Weight{});
w *= Weight(2);
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
const Weight inf = std::numeric_limits<Weight>::max() / 4;
struct shortest_path_result {
std::vector<Weight> dis;
std::vector<int> pre;
std::vector<int> pe;
};
auto sp = [&](int s, const std::vector<std::vector<adjacent_edge>> &G) {
int siz = int(G.size());
shortest_path_result res{std::vector<Weight>(siz, inf),
std::vector<int>(siz, -1),
std::vector<int>(siz, -1)};
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> q;
res.dis[s] = Weight{};
q.emplace(Weight{}, s);
while (!q.empty()) {
auto [dis, u] = q.top();
q.pop();
if (dis != res.dis[u]) {
continue;
}
for (auto [to, w, id] : G[u]) {
Weight can = dis + w;
if (can < res.dis[to]) {
res.dis[to] = can;
res.pre[to] = u;
res.pe[to] = id;
q.emplace(can, to);
}
}
}
return res;
};
std::vector<std::vector<Weight>> dis(n, std::vector<Weight>(n));
for (int s = 0; s < n; s++) {
dis[s] = sp(s, g).dis;
for (Weight val : dis[s]) {
assert(val != inf);
}
}
std::vector<std::vector<int>> ord(n, std::vector<int>(n));
Weight bvs = inf;
int bv = 0;
for (int u = 0; u < n; u++) {
for (int rhs = 0; rhs < n; rhs++) {
ord[u][rhs] = rhs;
}
std::stable_sort(ord[u].begin(), ord[u].end(),
[&](int a, int b) { return dis[u][a] > dis[u][b]; });
Weight va1 = dis[u][ord[u][0]] * Weight(2);
if (va1 < bvs) {
bvs = va1;
bv = u;
}
}
Weight bes = inf;
int be = -1;
int bu = -1;
int bw = -1;
Weight du{};
Weight dv{};
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w0] = es[id];
if (a == b) {
continue;
}
Weight w = w0 * Weight(2);
int prv = ord[a][0];
for (int u : ord[a]) {
if (dis[b][u] > dis[b][prv]) {
Weight va1 = dis[b][prv] + dis[a][u] + w;
if (va1 < bes) {
bes = va1;
be = id;
bu = a;
bw = b;
du = va1 / Weight(2) - dis[a][u];
dv = w - du;
}
prv = u;
}
}
}
minimum_diameter_spanning_tree_result<Weight> res;
if (bes < bvs) {
int o = n;
auto aug = g;
aug.emplace_back();
aug[o].push_back({bu, du, -1});
aug[o].push_back({bw, dv, -1});
auto tr = sp(o, aug);
res.dia = bes / Weight(2);
res.eid.reserve(n - 1);
for (int u = 0; u < n; u++) {
if (u != bu && u != bw) {
assert(tr.pe[u] >= 0);
res.eid.push_back(tr.pe[u]);
}
}
res.eid.push_back(be);
} else {
auto tr = sp(bv, g);
res.dia = bvs / Weight(2);
res.eid.reserve(n - 1);
for (int u = 0; u < n; u++) {
if (u != bv) {
assert(tr.pe[u] >= 0);
res.eid.push_back(tr.pe[u]);
}
}
}
return res;
}
} // namespace noya