Partition matroid （分割マトロイド）
(combinatorial_opt/matroids/partition_matroid.hpp)

• View this file on GitHub
• Last update: 2021-09-01 23:53:05+09:00
• Include: #include "combinatorial_opt/matroids/partition_matroid.hpp"

$e = 0, \dots, M - 1$ からなる $M$ 要素の集合 $E$ の分割 $E$ = $E_1 \cup \dots \cup E_K \, (E_i \cap E_j = \varnothing (i \neq j))$と，分割された各部分集合に対する上限要素数 $R_k \ge 0 \, (k = 0, \dots, K - 1)$ によって定められるマトロイド：

$\displaystyle \mathcal{I} = { I \subset E \mid |I \cup E_k| \le R_k \, (k = 0, \dots, K - 1) }. $

使用例

vector<vector<int>> grp; // 登場しない要素があってもよい（それらは制約なしとして扱われる）
grp.push_back({0, 2, 5});
grp.push_back({1, 3});
vector<int> lim{2, 1};
PartitionMatroid M(6, grp, lim);

assert(M.size() == 6);
vector<bool> I(6);
I[0] = I[1] = I[2] = 1;
M.set(I);
assert((M.circuit(5) == vector<int>{0, 2, 5}));

Verified with

• combinatorial_opt/test/matroid_intersection.aoj1605.test.cpp
• combinatorial_opt/test/matroid_intersection.aoj_grl_2_b.test.cpp
• combinatorial_opt/test/matroid_intersection_dijkstra.aoj1605.test.cpp
• combinatorial_opt/test/matroid_intersection_dijkstra.aoj_grl_2_b.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

// 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 2 "combinatorial_opt/matroids/partition_matroid.hpp"
#include <cassert>
#include <vector>

// 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 {};
    }
};

Back to top page