test/directed.test.cpp

View this file on GitHub
Last update: 2024-03-09 13:04:52+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_B"
#include <iostream>
#include "C++/graph/mst/directed.hpp"
int main() {
    int v, e, r;
    std::cin >> v >> e >> r;
    std::vector<edge> edges;
    while(e--) {
        int s, t, w;
        std::cin >> s >> t >> w;
        edges.emplace_back(s, t, -1, w);
    }
    std::cout << directed(edges, v, r).cost << '\n';
}

#line 1 "test/directed.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_B"
#include <iostream>
#line 2 "C++/graph/mst/directed.hpp"

#line 2 "C++/graph/mst/MST.hpp"

#include <vector>
#line 2 "C++/graph/edge.hpp"

struct edge {
    int src, to, id;
    long long cost;
    edge(){}
    edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
    operator int() const { return to; }
};

/**
 * @brief Edge
 */
#line 5 "C++/graph/mst/MST.hpp"
struct MST {
    std::vector<edge> tree;
    long long cost;
};

/**
 * @brief 最小全域木
 */
#line 2 "C++/other/SkewHeap.hpp"

#pragma GCC diagnostic ignored "-Wreorder"

#include <cassert>
#include <algorithm>
template <bool is_min = true> struct SkewHeap {
    struct Node {
        long long key, lazy;
        Node *l, *r;
        int idx;
        explicit Node(const long long &key, const int idx): key(key), idx(idx), lazy(0), l(nullptr), r(nullptr){}
    };
private:
    Node *alloc(const long long &key, int idx = -1) {
        return new Node(key, idx);
    }
    Node *propagate(Node *t) {
        if(t && t -> lazy != 0) {
            if(t -> l) {
                t -> l -> lazy += t -> lazy;
            }
            if(t -> r) {
                t -> r -> lazy += t -> lazy;
            }
            t -> key += t -> lazy;
            t -> lazy = 0;
        }
        return t;
    }
public:
    SkewHeap(){}
    Node *meld(Node *x, Node *y) {
        propagate(x), propagate(y);
        if(!x || !y) {
            return x ? x : y;
        }
        if((x -> key < y -> key) ^ is_min) {
            std::swap(x, y);
        }
        x -> r = meld(y, x -> r);
        std::swap(x -> l, x -> r);
        return x;
    }
    Node *push(Node *t, const long long &key, int idx = -1){ return meld(t, alloc(key, idx)); }
    Node *pop(Node *t) {
        assert(t);
        return meld(t -> l, t -> r);
    }
    Node *add(Node *t, const long long &lazy) {
        if(t) {
            t -> lazy += lazy;
            propagate(t);
        }
        return t;
    }
};

/**
 * @brief SkewHeap
 * @see https://ei1333.github.io/library/structure/heap/skew-heap.hpp
 */
#line 5 "C++/graph/mst/directed.hpp"
inline MST directed(std::vector<edge> edges, const int n, const int v) {
    for(int i = 0; i < n; ++i) {
        if(i != v) {
            edges.emplace_back(i, v, 0);
        }
    }
    int x = 0;
    std::vector<int> par(2 * n, -1), vis(par), link(par), st;
    using Node = typename SkewHeap<>::Node;
    SkewHeap heap;
    std::vector<Node*> ins(2 * n, nullptr);
    for(size_t i = 0; i < edges.size(); ++i) {
        const auto &e = edges[i];
        ins[e] = heap.push(ins[e], e.cost, i);
    }
    const auto go = [&](int z) -> int {
        z = edges[ins[z] -> idx].src;
        while(link[z] != -1) {
            st.emplace_back(z);
            z = link[z];
        }
        for(const auto &p : st) {
            link[p] = z;
        }
        st.clear();
        return z;
    };
    for(int i = n; ins[x]; ++i) {
        while(vis[x] == -1) {
            vis[x] = 0;
            x = go(x);
        }
        while(x != i) {
            const auto w = ins[x] -> key;
            auto z = heap.pop(ins[x]);
            z = heap.add(z, -w);
            ins[i] = heap.meld(ins[i], z);
            par[x] = i;
            link[x] = i;
            x = go(x);
        }
        while(ins[x] && go(x) == x) {
            ins[x] = heap.pop(ins[x]);
        }
    }
    for(int i = v; i != -1; i = par[i]) {
		vis[i] = 1;
	}
    long long cost = 0;
    std::vector<edge> e;
    for(int i = x; i >= 0; i--) {
		if(vis[i] == 1) {
			continue;
		}
        cost += edges[ins[i] -> idx].cost;
        e.emplace_back(edges[ins[i] -> idx]);
        for(int j = edges[ins[i] -> idx]; j != -1 && vis[j] == 0; j = par[j]) {
            vis[j] = 1;
        }
    }
    return {e, cost};
}

/**
 * @brief Directed MST
 * @see https://ei1333.github.io/library/graph/mst/directed-mst.hpp
 */
#line 4 "test/directed.test.cpp"
int main() {
    int v, e, r;
    std::cin >> v >> e >> r;
    std::vector<edge> edges;
    while(e--) {
        int s, t, w;
        std::cin >> s >> t >> w;
        edges.emplace_back(s, t, -1, w);
    }
    std::cout << directed(edges, v, r).cost << '\n';
}