#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559"
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
#include "Mylib/DataStructure/Heap/pairing_heap.cpp"
#include "Mylib/Graph/MinimumSpanningTree/prim.cpp"
#include "Mylib/Graph/Template/graph.cpp"
#include "Mylib/Misc/merge_technique.cpp"
#include "Mylib/Utils/fix_point.cpp"
namespace hl = haar_lib;
int main() {
int n, m;
std::cin >> n >> m;
hl::graph<int64_t> g(n);
g.read<1, false>(m);
std::map<std::pair<int, int>, int> index;
for (auto &a : g) {
for (auto &e : a) index[{e.from, e.to}] = e.index;
}
auto res = hl::prim(g);
std::vector<int64_t> ans(m, -1);
if ((int) res.size() == n - 1) {
int64_t s = 0;
hl::tree<int64_t> tree(n);
for (auto &e : res) {
s += e.cost;
tree[e.from].push_back(e);
}
ans.assign(m, s);
std::vector<hl::pairing_heap<std::tuple<int64_t, int, int>, std::greater<>>> heaps(n);
std::vector<std::set<int>> sub(n);
hl::make_fix_point(
[&](auto &&f, int cur, int par, int64_t cost) -> void {
for (auto &e : g[cur]) {
heaps[cur].push({e.cost, e.from, e.to});
}
sub[cur].insert(cur);
for (auto &e : tree[cur]) {
if (e.to == par) continue;
f(e.to, cur, e.cost);
heaps[cur].meld(heaps[e.to]);
hl::merge_technique(sub[cur], sub[cur], sub[e.to]);
}
if (par != -1) {
while (not heaps[cur].empty()) {
auto [c, i, j] = heaps[cur].top();
if ((sub[cur].find(i) != sub[cur].end() and sub[cur].find(j) != sub[cur].end()) or
(i == cur and j == par) or (i == par and j == cur)) {
heaps[cur].pop();
} else {
break;
}
}
if (not heaps[cur].empty()) {
ans[index[{cur, par}]] = s - cost + std::get<0>(heaps[cur].top());
} else {
ans[index[{cur, par}]] = -1;
}
}
})(0, -1, 0);
}
for (auto x : ans) {
std::cout << x << std::endl;
}
return 0;
}
#line 1 "test/aoj/2559/main.pairing_heap.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559"
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
#line 2 "Mylib/DataStructure/Heap/pairing_heap.cpp"
#include <functional>
#line 4 "Mylib/DataStructure/Heap/pairing_heap.cpp"
namespace haar_lib {
template <typename T, typename Compare = std::less<T>>
class pairing_heap {
public:
using value_type = T;
private:
struct node_ {
T value;
std::vector<node_ *> ch;
node_(const T &value) : value(value) {}
};
Compare compare_;
node_ *root_ = nullptr;
size_t size_ = 0;
node_ *merge_(node_ *a, node_ *b) {
if (not a) return b;
if (not b) return a;
if (compare_(b->value, a->value)) {
a->ch.push_back(b);
return a;
} else {
b->ch.push_back(a);
return b;
}
}
node_ *merge_list_(node_ *a) {
if ((a->ch.size() & 1) == 1) a->ch.push_back(nullptr);
for (size_t i = 0; i < a->ch.size(); i += 2) {
a->ch[i >> 1] = merge_(a->ch[i], a->ch[i + 1]);
}
a->ch.resize(a->ch.size() / 2);
node_ *ret = nullptr;
for (int i = a->ch.size(); --i >= 0;) {
ret = merge_(ret, a->ch[i]);
}
return ret;
}
public:
pairing_heap() : compare_(Compare()) {}
pairing_heap(const Compare &compare_) : compare_(compare_) {}
void meld(pairing_heap &that) {
root_ = merge_(root_, that.root_);
that.root_ = nullptr;
size_ += that.size_;
that.size_ = 0;
}
void push(const T &val) {
root_ = merge_(root_, new node_(val));
++size_;
}
void pop() {
root_ = merge_list_(root_);
--size_;
}
const T &top() const { return root_->value; }
bool empty() const { return root_ == nullptr; }
size_t size() const { return size_; }
};
} // namespace haar_lib
#line 2 "Mylib/Graph/MinimumSpanningTree/prim.cpp"
#include <queue>
#line 4 "Mylib/Graph/Template/graph.cpp"
namespace haar_lib {
template <typename T>
struct edge {
int from, to;
T cost;
int index = -1;
edge() {}
edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
edge(int from, int to, T cost, int index) : from(from), to(to), cost(cost), index(index) {}
};
template <typename T>
struct graph {
using weight_type = T;
using edge_type = edge<T>;
std::vector<std::vector<edge<T>>> data;
auto& operator[](size_t i) { return data[i]; }
const auto& operator[](size_t i) const { return data[i]; }
auto begin() const { return data.begin(); }
auto end() const { return data.end(); }
graph() {}
graph(int N) : data(N) {}
bool empty() const { return data.empty(); }
int size() const { return data.size(); }
void add_edge(int i, int j, T w, int index = -1) {
data[i].emplace_back(i, j, w, index);
}
void add_undirected(int i, int j, T w, int index = -1) {
add_edge(i, j, w, index);
add_edge(j, i, w, index);
}
template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>
void read(int M) {
for (int i = 0; i < M; ++i) {
int u, v;
std::cin >> u >> v;
u -= I;
v -= I;
T w = 1;
if (WEIGHTED) std::cin >> w;
if (DIRECTED)
add_edge(u, v, w, i);
else
add_undirected(u, v, w, i);
}
}
};
template <typename T>
using tree = graph<T>;
} // namespace haar_lib
#line 5 "Mylib/Graph/MinimumSpanningTree/prim.cpp"
namespace haar_lib {
template <typename T>
std::vector<edge<T>> prim(const graph<T> &graph) {
const int n = graph.size();
std::vector<bool> visit(n, false);
std::vector<edge<T>> ret;
auto cmp = [](const auto &a, const auto &b) { return a.cost > b.cost; };
std::priority_queue<edge<T>, std::vector<edge<T>>, decltype(cmp)> pq(cmp);
visit[0] = true;
for (auto &e : graph[0]) pq.push(e);
while (not pq.empty()) {
auto t = pq.top();
pq.pop();
if (visit[t.from] == visit[t.to]) continue;
int i = visit[t.from] ? t.to : t.from;
for (auto &e : graph[i]) {
pq.push(e);
}
visit[i] = true;
ret.push_back(t);
}
return ret;
}
} // namespace haar_lib
#line 3 "Mylib/Misc/merge_technique.cpp"
#include <utility>
namespace haar_lib {
template <typename T>
void merge_technique(std::set<T> &res, std::set<T> &a, std::set<T> &b) {
if (a.size() > b.size()) {
a.insert(b.begin(), b.end());
std::swap(res, a);
} else {
b.insert(a.begin(), a.end());
std::swap(res, b);
}
}
} // namespace haar_lib
#line 3 "Mylib/Utils/fix_point.cpp"
namespace haar_lib {
template <typename F>
struct fix_point : F {
explicit constexpr fix_point(F &&f) noexcept : F(std::forward<F>(f)) {}
template <typename... Args>
constexpr auto operator()(Args &&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <typename F>
inline constexpr auto make_fix_point(F &&f) {
return fix_point<F>(std::forward<F>(f));
}
template <typename F>
inline constexpr auto make_fix_point(F &f) {
return fix_point<F>(std::forward<F>(f));
}
} // namespace haar_lib
#line 13 "test/aoj/2559/main.pairing_heap.test.cpp"
namespace hl = haar_lib;
int main() {
int n, m;
std::cin >> n >> m;
hl::graph<int64_t> g(n);
g.read<1, false>(m);
std::map<std::pair<int, int>, int> index;
for (auto &a : g) {
for (auto &e : a) index[{e.from, e.to}] = e.index;
}
auto res = hl::prim(g);
std::vector<int64_t> ans(m, -1);
if ((int) res.size() == n - 1) {
int64_t s = 0;
hl::tree<int64_t> tree(n);
for (auto &e : res) {
s += e.cost;
tree[e.from].push_back(e);
}
ans.assign(m, s);
std::vector<hl::pairing_heap<std::tuple<int64_t, int, int>, std::greater<>>> heaps(n);
std::vector<std::set<int>> sub(n);
hl::make_fix_point(
[&](auto &&f, int cur, int par, int64_t cost) -> void {
for (auto &e : g[cur]) {
heaps[cur].push({e.cost, e.from, e.to});
}
sub[cur].insert(cur);
for (auto &e : tree[cur]) {
if (e.to == par) continue;
f(e.to, cur, e.cost);
heaps[cur].meld(heaps[e.to]);
hl::merge_technique(sub[cur], sub[cur], sub[e.to]);
}
if (par != -1) {
while (not heaps[cur].empty()) {
auto [c, i, j] = heaps[cur].top();
if ((sub[cur].find(i) != sub[cur].end() and sub[cur].find(j) != sub[cur].end()) or
(i == cur and j == par) or (i == par and j == cur)) {
heaps[cur].pop();
} else {
break;
}
}
if (not heaps[cur].empty()) {
ans[index[{cur, par}]] = s - cost + std::get<0>(heaps[cur].top());
} else {
ans[index[{cur, par}]] = -1;
}
}
})(0, -1, 0);
}
for (auto x : ans) {
std::cout << x << std::endl;
}
return 0;
}
test/aoj/2559/main.pairing_heap.test.cpp
Prim algorithm
(Mylib/Graph/MinimumSpanningTree/prim.cpp)