cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: combinatorial_opt/test/matroid_intersection_dijkstra.aoj_grl_2_b.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B"
#include "../matroid_intersection_dijkstra.hpp"
#include "../matroids/graphic_matroid.hpp"
#include "../matroids/partition_matroid.hpp"
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int V, E, r;
    cin >> V >> E >> r;
    vector<vector<int>> partition(V);
    vector<int> R(V, 1);
    R.at(r) = 0;
    vector<pair<int, int>> edges;
    vector<int> weight;
    for (int e = 0; e < E; ++e) {
        int s, t, w;
        cin >> s >> t >> w;
        partition.at(t).push_back(e);
        edges.emplace_back(s, t);
        weight.emplace_back(-w);
    }
    PartitionMatroid M1(E, partition, R);
    GraphicMatroid M2(V, edges);

    vector<int> potential(weight.size());
    vector<bool> sol(weight.size());
    while (augment_matroid_intersection_dijkstra(M1, M2, sol, weight, potential)) continue;

    int ret = 0;
    for (int e = 0; e < E; ++e) ret -= sol.at(e) * weight.at(e);
    cout << ret << '\n';
}
#line 1 "combinatorial_opt/test/matroid_intersection_dijkstra.aoj_grl_2_b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B"
#line 2 "combinatorial_opt/matroid_intersection_dijkstra.hpp"

#include <cassert>
#include <queue>
#include <vector>

// Find maximum weight size k + 1 intersection of two matroids using Dijkstra's algorithm
// Return `true` iff larger intersection is found.
// Complexity: O(Cn + nk log n) (C: circuit query)
template <class Matroid1, class Matroid2, class T = int>
bool augment_matroid_intersection_dijkstra(
    Matroid1 &m1,                 // Matroid, size n, updated
    Matroid2 &m2,                 // Matroid, size n, updated
    std::vector<bool> &I,         // Size k maximum weight intersection, size n, updated
    const std::vector<T> &weight, // Weights of elements, size n
    std::vector<T> &potential     // Potential, size n + 2, updated
) {
    const int n = I.size();

    assert((int)m1.size() == n);
    assert((int)m2.size() == n);
    assert((int)weight.size() == n);
    assert(potential.empty() or ((int)potential.size() == n) or ((int)potential.size() == n + 2));

    m1.set(I);
    m2.set(I);

    potential.resize(n + 2);

    auto l = [&](int e) -> T { return e < n ? (I.at(e) ? weight.at(e) : -weight.at(e)) : T(); };
    auto edge_len = [&](int s, int t) -> T { return l(t) - potential.at(t) + potential.at(s); };

    if (true) { // 自明な追加が可能かチェック（省略してもアルゴリズムは正当）
        int max_elem = -1;
        for (int e = 0; e < n; ++e) {
            if (!I.at(e) and (max_elem < 0 or weight.at(max_elem) < weight.at(e))) max_elem = e;
        }
        if (max_elem < 0) return false;
        for (int e = 0; e < n; ++e) {
            if (!I.at(e) and weight.at(e) == weight.at(max_elem) and m1.circuit(e).empty() and
                m2.circuit(e).empty()) {
                potential.at(e) -= l(e);
                I.at(e) = true;
                return true;
            }
        }
    }

    // Find minimum length (& minimum num. of vertices) gs-gt path
    const int gs = n, gt = n + 1;
    std::vector<std::vector<int>> to(gt + 1);

    bool has_gs_edge = false, has_gt_edge = false;

    for (int e = 0; e < n; ++e) {
        if (I.at(e)) continue;

        const auto c1 = m1.circuit(e), c2 = m2.circuit(e);

        if (c1.empty()) {
            to.at(e).push_back(gt);
            if (!has_gt_edge) {
                has_gt_edge = true;
                potential.at(gt) = potential.at(e);
            }
            if (T el = edge_len(e, gt); el < T()) potential.at(gt) += el;
        }
        for (int f : c1) {
            if (f != e) to.at(e).push_back(f);
        }

        if (c2.empty()) {
            to.at(gs).push_back(e);
            if (!has_gs_edge) {
                has_gs_edge = true;
                potential.at(gs) = potential.at(e) - l(e);
            }
            if (T el = edge_len(gs, e); el < T()) potential.at(gs) -= el;
        }
        for (int f : c2) {
            if (f != e) to.at(f).push_back(e);
        }
    }

    if (const T e0 = potential.at(gs); e0 != T()) {
        for (auto &p : potential) p -= e0;
    }

    if (!has_gs_edge or !has_gt_edge) return false;

    std::vector<bool> potential_fixed(gt + 1);

    T potential_add_unfixed_es = T();

    auto fix_potential = [&](int e) -> void {
        assert(!potential_fixed.at(e));
        potential_fixed.at(e) = true;
        potential.at(e) += potential_add_unfixed_es;
    };

    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<>> pq;
    std::vector<T> dijkstra(gt + 1);
    std::vector<int> prv(gt + 1, -1);

    pq.emplace(T(), gs);

    while (!pq.empty()) {
        const int e = pq.top().second;
        pq.pop();
        if (potential_fixed.at(e)) continue;
        if (e != gs) potential_add_unfixed_es = edge_len(prv.at(e), e);

        std::vector<std::pair<int, int>> push_cands;

        auto rec = [&](auto &&self, int cur) -> bool {
            if (cur == gt) return true;
            fix_potential(cur);

            for (int nxt : to.at(cur)) {
                if (potential_fixed.at(nxt)) continue;

                const T len = edge_len(cur, nxt) - potential_add_unfixed_es;
                // if (len < T()) std::cerr << cur << ' ' << nxt << ' ' << len << std::endl;
                assert(len >= T());

                if (len == T()) {
                    prv.at(nxt) = cur;
                    if (self(self, nxt)) return true;
                } else {
                    if (prv.at(nxt) == -1 or potential_add_unfixed_es + len < dijkstra.at(nxt)) {
                        dijkstra.at(nxt) = potential_add_unfixed_es + len;
                        prv.at(nxt) = cur;
                        push_cands.emplace_back(nxt, cur);
                    }
                }
            }
            return false;
        };
        if (rec(rec, e)) break;

        for (auto [nxt, now] : push_cands) {
            if (prv.at(nxt) == now) pq.emplace(dijkstra.at(nxt), nxt);
        }
    }

    for (int e = 0; e < gt + 1; ++e) {
        if (!potential_fixed.at(e)) fix_potential(e);
    }

    if (prv.at(gt) < 0) return false;

    prv.assign(gt + 1, -1);
    std::queue<int> q;
    q.push(gs);

    for (int now = q.front(); now != gt; now = q.front()) {
        q.pop();
        for (int nxt : to.at(now)) {
            if (prv.at(nxt) == -1 and edge_len(now, nxt) == T()) {
                prv.at(nxt) = now;
                q.push(nxt);
            }
        }
    }

    for (int e = prv.at(gt); e != gs; e = prv.at(e)) {
        potential.at(e) -= l(e);
        I.at(e) = !I.at(e);
    }

    return true;
}
#line 3 "combinatorial_opt/matroids/graphic_matroid.hpp"
#include <utility>
#line 5 "combinatorial_opt/matroids/graphic_matroid.hpp"

// GraphicMatroid: subgraph of undirected graphs, without loops
class GraphicMatroid {
    using Vertex = int;
    using Element = int;
    int M;
    int V; // # of vertices of graph
    std::vector<std::vector<std::pair<Vertex, Element>>> to;
    std::vector<std::pair<Vertex, Vertex>> edges;
    std::vector<Element> backtrack;
    std::vector<Vertex> vprev;
    std::vector<int> depth, root;

public:
    GraphicMatroid(int V, const std::vector<std::pair<Vertex, Vertex>> &edges_)
        : M(edges_.size()), V(V), to(V), edges(edges_) {
        for (int e = 0; e < int(edges_.size()); e++) {
            int u = edges_[e].first, v = edges_[e].second;
            assert(0 <= u and u < V);
            assert(0 <= v and v < V);
            if (u != v) {
                to[u].emplace_back(v, e);
                to[v].emplace_back(u, e);
            }
        }
    }
    int size() const { return M; }

    std::vector<Vertex> que;
    template <class State> void set(State I) {
        assert(int(I.size()) == M);
        backtrack.assign(V, -1);
        vprev.assign(V, -1);
        depth.assign(V, -1);
        root.assign(V, -1);
        que.resize(V);
        int qb = 0, qe = 0;
        for (Vertex i = 0; i < V; i++) {
            if (backtrack[i] >= 0) continue;
            que[qb = 0] = i, qe = 1, depth[i] = 0;
            while (qb < qe) {
                Vertex now = que[qb++];
                root[now] = i;
                for (auto nxt : to[now]) {
                    if (depth[nxt.first] < 0 and I[nxt.second]) {
                        backtrack[nxt.first] = nxt.second;
                        vprev[nxt.first] = now;
                        depth[nxt.first] = depth[now] + 1;
                        que[qe++] = nxt.first;
                    }
                }
            }
        }
    }

    std::vector<Element> circuit(const Element e) const {
        assert(0 <= e and e < M);
        Vertex s = edges[e].first, t = edges[e].second;
        if (root[s] != root[t]) return {};
        std::vector<Element> ret{e};
        auto step = [&](Vertex &i) { ret.push_back(backtrack[i]), i = vprev[i]; };
        int ddepth = depth[s] - depth[t];
        for (; ddepth > 0; --ddepth) step(s);
        for (; ddepth < 0; ++ddepth) step(t);
        while (s != t) step(s), step(t);
        return ret;
    }
};
#line 4 "combinatorial_opt/matroids/partition_matroid.hpp"

// Partition matroid (partitional matroid) : direct sum of uniform matroids
class PartitionMatroid {
    using Element = int;
    int M;
    std::vector<std::vector<Element>> parts;
    std::vector<int> belong;
    std::vector<int> R;
    std::vector<int> cnt;
    std::vector<std::vector<Element>> circuits;

public:
    // parts: partition of [0, 1, ..., M - 1]
    // R: only R[i] elements from parts[i] can be chosen for each i.
    PartitionMatroid(int M, const std::vector<std::vector<int>> &parts_, const std::vector<int> &R_)
        : M(M), parts(parts_), belong(M, -1), R(R_) {
        assert(parts.size() == R.size());
        for (int i = 0; i < int(parts.size()); i++) {
            for (Element e : parts[i]) belong[e] = i;
        }
        for (Element e = 0; e < M; e++) {
            // assert(belong[e] != -1);
            if (belong[e] == -1) {
                belong[e] = parts.size();
                parts.push_back({e});
                R.push_back(1);
            }
        }
    }
    int size() const { return M; }

    template <class State> void set(const State &I) {
        cnt = R;
        for (int e = 0; e < M; e++) {
            if (I[e]) cnt[belong[e]]--;
        }
        circuits.assign(cnt.size(), {});
        for (int e = 0; e < M; e++) {
            if (I[e] and cnt[belong[e]] == 0) circuits[belong[e]].push_back(e);
        }
    }

    std::vector<Element> circuit(const Element e) const {
        assert(0 <= e and e < M);
        int p = belong[e];
        if (cnt[p] == 0) {
            auto ret = circuits[p];
            ret.push_back(e);
            return ret;
        }
        return {};
    }
};
#line 5 "combinatorial_opt/test/matroid_intersection_dijkstra.aoj_grl_2_b.test.cpp"
#include <iostream>
#line 8 "combinatorial_opt/test/matroid_intersection_dijkstra.aoj_grl_2_b.test.cpp"
using namespace std;

int main() {
    int V, E, r;
    cin >> V >> E >> r;
    vector<vector<int>> partition(V);
    vector<int> R(V, 1);
    R.at(r) = 0;
    vector<pair<int, int>> edges;
    vector<int> weight;
    for (int e = 0; e < E; ++e) {
        int s, t, w;
        cin >> s >> t >> w;
        partition.at(t).push_back(e);
        edges.emplace_back(s, t);
        weight.emplace_back(-w);
    }
    PartitionMatroid M1(E, partition, R);
    GraphicMatroid M2(V, edges);

    vector<int> potential(weight.size());
    vector<bool> sol(weight.size());
    while (augment_matroid_intersection_dijkstra(M1, M2, sol, weight, potential)) continue;

    int ret = 0;
    for (int e = 0; e < E; ++e) ret -= sol.at(e) * weight.at(e);
    cout << ret << '\n';
}
Back to top page