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.aoj1605.test.cpp

Depends on

Code

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    while (true) {
        int N, M, K;
        cin >> N >> M >> K;
        if (N == 0) break;
        vector<vector<int>> partition(2);
        vector<int> R{K, N - 1 - K};
        vector<pair<int, int>> edges;
        vector<int> weight;
        for (int e = 0; e < M; ++e) {
            int u, v, w;
            char l;
            cin >> u >> v >> w >> l;
            --u, --v;
            partition[l == 'B'].push_back(e);
            edges.emplace_back(u, v);
            weight.push_back(-w);
        }
        PartitionMatroid M1(edges.size(), partition, R);
        GraphicMatroid M2(N, edges);

        vector<int> potential(weight.size());
        vector<bool> ret(weight.size());
        while (augment_matroid_intersection_dijkstra(M1, M2, ret, weight, potential)) continue;
        int ne = accumulate(ret.begin(), ret.end(), 0);
        if (ne < N - 1) {
            cout << "-1\n";
        } else {
            int sum = 0;
            for (int e = 0; e < M; ++e) sum -= ret.at(e) * weight.at(e);
            cout << sum << '\n';
        }
    }
}
#line 1 "combinatorial_opt/test/matroid_intersection_dijkstra.aoj1605.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1605"
#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.aoj1605.test.cpp"
#include <iostream>
#include <numeric>
#line 9 "combinatorial_opt/test/matroid_intersection_dijkstra.aoj1605.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    while (true) {
        int N, M, K;
        cin >> N >> M >> K;
        if (N == 0) break;
        vector<vector<int>> partition(2);
        vector<int> R{K, N - 1 - K};
        vector<pair<int, int>> edges;
        vector<int> weight;
        for (int e = 0; e < M; ++e) {
            int u, v, w;
            char l;
            cin >> u >> v >> w >> l;
            --u, --v;
            partition[l == 'B'].push_back(e);
            edges.emplace_back(u, v);
            weight.push_back(-w);
        }
        PartitionMatroid M1(edges.size(), partition, R);
        GraphicMatroid M2(N, edges);

        vector<int> potential(weight.size());
        vector<bool> ret(weight.size());
        while (augment_matroid_intersection_dijkstra(M1, M2, ret, weight, potential)) continue;
        int ne = accumulate(ret.begin(), ret.end(), 0);
        if (ne < N - 1) {
            cout << "-1\n";
        } else {
            int sum = 0;
            for (int e = 0; e < M; ++e) sum -= ret.at(e) * weight.at(e);
            cout << sum << '\n';
        }
    }
}
Back to top page