#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/leftist_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::leftist_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.leftist_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/leftist_heap.cpp"
#include <functional>
#include <utility>
namespace haar_lib {
template <typename T, class Compare = std::less<T>>
class leftist_heap {
public:
using value_type = T;
private:
struct node {
T val;
node *left, *right;
int s, size;
node(const T &val) : val(val), left(nullptr), right(nullptr), s(0), size(1) {}
};
node *root_;
Compare compare_;
public:
leftist_heap() : root_(nullptr), compare_(Compare()) {}
leftist_heap(const Compare &compare_) : root_(nullptr), compare_(compare_) {}
protected:
node *meld(node *a, node *b) {
if (not a) return b;
if (not b) return a;
if (compare_(a->val, b->val)) std::swap(a, b);
a->right = meld(a->right, b);
if (not a->left or a->left->s < a->right->s) std::swap(a->left, a->right);
a->s = (a->right ? a->right->s : 0) + 1;
a->size = 1 + (a->left ? a->left->size : 0) + (a->right ? a->right->size : 0);
return a;
}
public:
void meld(leftist_heap &heap) {
root_ = meld(root_, heap.root_);
heap.root_ = nullptr;
}
void push(const T &val) { root_ = meld(root_, new node(val)); }
const T &top() const { return root_->val; }
void pop() {
node *temp = root_;
root_ = meld(root_->left, root_->right);
delete temp;
}
bool empty() const { return root_ == nullptr; }
size_t size() const { return root_ ? root_->size : 0; }
};
} // 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 4 "Mylib/Misc/merge_technique.cpp"
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.leftist_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::leftist_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.leftist_heap.test.cpp
Prim algorithm
(Mylib/Graph/MinimumSpanningTree/prim.cpp)