Matroid All
(matroid/all.hpp)
- View this file on GitHub
- Last update: 2026-07-29 16:26:14+09:00
- Include:
#include "matroid/all.hpp"
Overview
matroid/all.hpp includes the standard matroid independence oracles, general
weighted and unweighted matroid intersection, and the concise randomized
cardinality algorithm for two linear matroids.
Every oracle accepts a const std::vector<int>& subset and can be passed
directly to m1une::matroid::matroid_intersection.
Oracle subsets must contain distinct valid ground-set indices. The intersection algorithm always satisfies this precondition.
Included Headers
| Header | Contents |
|---|---|
matroid/uniform_matroid.hpp |
Uniform matroid $U_{r,n}$. |
matroid/partition_matroid.hpp |
Per-group capacity constraints. |
matroid/graphic_matroid.hpp |
Forest independence on graph edges. |
matroid/linear_matroid.hpp |
General field and 64-bit binary linear matroids. |
matroid/linear_matroid_intersection.hpp |
Randomized maximum cardinality for the intersection of two linear matroids. |
matroid/matroid_intersection.hpp |
Maximum-cardinality common independent set. |
matroid/weighted_matroid_intersection.hpp |
Minimum- or maximum-weight common independent set among those of maximum cardinality. |
Example
#include "matroid/all.hpp"
#include <vector>
int main() {
m1une::matroid::UniformMatroid at_most_three(6, 3);
m1une::matroid::PartitionMatroid one_per_group(
std::vector<int>{0, 0, 1, 1, 2, 2});
auto result = m1une::matroid::matroid_intersection(
6, at_most_three, one_per_group);
}
Depends on
- Graphic Matroid
(matroid/graphic_matroid.hpp)
- Linear Matroid
(matroid/linear_matroid.hpp)
- Linear Matroid Intersection
(matroid/linear_matroid_intersection.hpp)
- Matroid Intersection
(matroid/matroid_intersection.hpp)
- Partition Matroid
(matroid/partition_matroid.hpp)
- Uniform Matroid
(matroid/uniform_matroid.hpp)
- Weighted Matroid Intersection
(matroid/weighted_matroid_intersection.hpp)
Verified with
Code
#ifndef M1UNE_MATROID_ALL_HPP
#define M1UNE_MATROID_ALL_HPP 1
#include "graphic_matroid.hpp"
#include "linear_matroid.hpp"
#include "linear_matroid_intersection.hpp"
#include "matroid_intersection.hpp"
#include "partition_matroid.hpp"
#include "uniform_matroid.hpp"
#include "weighted_matroid_intersection.hpp"
#endif // M1UNE_MATROID_ALL_HPP#line 1 "matroid/all.hpp"
#line 1 "matroid/graphic_matroid.hpp"
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
namespace m1une {
namespace matroid {
class GraphicMatroid {
private:
int _vertex_count;
std::vector<std::pair<int, int>> _edges;
public:
GraphicMatroid() : _vertex_count(0) {}
GraphicMatroid(int vertex_count, std::vector<std::pair<int, int>> edges)
: _vertex_count(vertex_count), _edges(std::move(edges)) {
assert(0 <= vertex_count);
#ifndef NDEBUG
for (auto [u, v] : _edges) {
assert(0 <= u && u < _vertex_count);
assert(0 <= v && v < _vertex_count);
}
#endif
}
int size() const {
return int(_edges.size());
}
int vertex_count() const {
return _vertex_count;
}
const std::vector<std::pair<int, int>>& edges() const {
return _edges;
}
bool independent(const std::vector<int>& subset) const {
std::vector<int> parent_or_size(_vertex_count, -1);
auto leader = [&](auto&& self, int v) -> int {
if (parent_or_size[v] < 0) return v;
return parent_or_size[v] = self(self, parent_or_size[v]);
};
for (int element : subset) {
assert(0 <= element && element < int(_edges.size()));
auto [u, v] = _edges[element];
u = leader(leader, u);
v = leader(leader, v);
if (u == v) return false;
if (-parent_or_size[u] < -parent_or_size[v]) std::swap(u, v);
parent_or_size[u] += parent_or_size[v];
parent_or_size[v] = u;
}
return true;
}
bool operator()(const std::vector<int>& subset) const {
return independent(subset);
}
};
} // namespace matroid
} // namespace m1une
#line 1 "matroid/linear_matroid.hpp"
#include <array>
#line 6 "matroid/linear_matroid.hpp"
#include <cstdint>
#line 9 "matroid/linear_matroid.hpp"
namespace m1une {
namespace matroid {
template <class Field>
class LinearMatroid {
private:
int _dimension;
std::vector<std::vector<Field>> _vectors;
public:
LinearMatroid() : _dimension(0) {}
explicit LinearMatroid(std::vector<std::vector<Field>> vectors)
: _dimension(vectors.empty() ? 0 : int(vectors[0].size())),
_vectors(std::move(vectors)) {
#ifndef NDEBUG
for (const auto& vector : _vectors) assert(int(vector.size()) == _dimension);
#endif
}
int size() const {
return int(_vectors.size());
}
int dimension() const {
return _dimension;
}
const std::vector<std::vector<Field>>& vectors() const {
return _vectors;
}
bool independent(const std::vector<int>& subset) const {
if (int(subset.size()) > _dimension) return false;
std::vector<std::vector<Field>> basis(_dimension);
std::vector<char> has_pivot(_dimension, false);
for (int element : subset) {
assert(0 <= element && element < int(_vectors.size()));
std::vector<Field> vector = _vectors[element];
bool inserted = false;
for (int column = 0; column < _dimension; column++) {
if (vector[column] == Field(0)) continue;
if (!has_pivot[column]) {
Field inverse = Field(1) / vector[column];
for (int j = column; j < _dimension; j++) vector[j] *= inverse;
basis[column] = std::move(vector);
has_pivot[column] = true;
inserted = true;
break;
}
Field factor = vector[column];
for (int j = column; j < _dimension; j++) {
vector[j] -= factor * basis[column][j];
}
}
if (!inserted) return false;
}
return true;
}
bool operator()(const std::vector<int>& subset) const {
return independent(subset);
}
};
class BinaryLinearMatroid {
private:
std::vector<std::uint64_t> _vectors;
public:
BinaryLinearMatroid() = default;
explicit BinaryLinearMatroid(std::vector<std::uint64_t> vectors)
: _vectors(std::move(vectors)) {}
int size() const {
return int(_vectors.size());
}
int dimension() const {
return 64;
}
const std::vector<std::uint64_t>& vectors() const {
return _vectors;
}
bool independent(const std::vector<int>& subset) const {
if (subset.size() > 64) return false;
std::array<std::uint64_t, 64> basis = {};
for (int element : subset) {
assert(0 <= element && element < int(_vectors.size()));
std::uint64_t value = _vectors[element];
for (int bit = 63; bit >= 0; bit--) {
if ((value >> bit & 1) == 0) continue;
if (basis[bit] == 0) {
basis[bit] = value;
break;
}
value ^= basis[bit];
}
if (value == 0) return false;
}
return true;
}
bool operator()(const std::vector<int>& subset) const {
return independent(subset);
}
};
} // namespace matroid
} // namespace m1une
#line 1 "matroid/linear_matroid_intersection.hpp"
#line 5 "matroid/linear_matroid_intersection.hpp"
#include <chrono>
#line 9 "matroid/linear_matroid_intersection.hpp"
namespace m1une {
namespace matroid {
namespace internal {
inline std::uint64_t linear_matroid_intersection_random() {
static std::uint64_t state = std::uint64_t(
std::chrono::steady_clock::now().time_since_epoch().count());
state += 0x9e3779b97f4a7c15ULL;
std::uint64_t value = state;
value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
return value ^ (value >> 31);
}
template <class Field>
int linear_matroid_intersection_matrix_rank(
std::vector<std::vector<Field>> matrix) {
const int row_count = int(matrix.size());
const int column_count = row_count == 0 ? 0 : int(matrix[0].size());
int rank = 0;
for (int column = 0; column < column_count && rank < row_count; column++) {
int pivot = rank;
while (pivot < row_count && matrix[pivot][column] == Field(0)) pivot++;
if (pivot == row_count) continue;
std::swap(matrix[rank], matrix[pivot]);
Field inverse = Field(1) / matrix[rank][column];
for (int j = column; j < column_count; j++) matrix[rank][j] *= inverse;
for (int row = rank + 1; row < row_count; row++) {
if (matrix[row][column] == Field(0)) continue;
Field factor = matrix[row][column];
for (int j = column; j < column_count; j++) {
matrix[row][j] -= factor * matrix[rank][j];
}
}
rank++;
}
return rank;
}
} // namespace internal
template <class Field>
int linear_matroid_intersection_size_with_weights(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
const std::vector<Field>& weights) {
const int ground_size = int(first_vectors.size());
assert(int(second_vectors.size()) == ground_size);
assert(int(weights.size()) == ground_size);
if (ground_size == 0) return 0;
const int first_dimension = int(first_vectors[0].size());
const int second_dimension = int(second_vectors[0].size());
#ifndef NDEBUG
for (const auto& vector : first_vectors) {
assert(int(vector.size()) == first_dimension);
}
for (const auto& vector : second_vectors) {
assert(int(vector.size()) == second_dimension);
}
#endif
const bool transpose = second_dimension < first_dimension;
const int row_count = transpose ? second_dimension : first_dimension;
const int column_count = transpose ? first_dimension : second_dimension;
std::vector<std::vector<Field>> matrix(
row_count, std::vector<Field>(column_count, Field(0)));
for (int element = 0; element < ground_size; element++) {
const auto& row_vector =
transpose ? second_vectors[element] : first_vectors[element];
const auto& column_vector =
transpose ? first_vectors[element] : second_vectors[element];
for (int row = 0; row < row_count; row++) {
Field coefficient = weights[element] * row_vector[row];
if (coefficient == Field(0)) continue;
for (int column = 0; column < column_count; column++) {
matrix[row][column] += coefficient * column_vector[column];
}
}
}
return internal::linear_matroid_intersection_matrix_rank(std::move(matrix));
}
template <class Field, class RandomNumberGenerator>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors,
RandomNumberGenerator& random) {
assert(first_vectors.size() == second_vectors.size());
std::vector<Field> weights(first_vectors.size());
for (Field& weight : weights) weight = Field(random());
return linear_matroid_intersection_size_with_weights(
first_vectors, second_vectors, weights);
}
template <class Field>
int linear_matroid_intersection_size(
const std::vector<std::vector<Field>>& first_vectors,
const std::vector<std::vector<Field>>& second_vectors) {
assert(first_vectors.size() == second_vectors.size());
std::vector<Field> weights(first_vectors.size());
for (Field& weight : weights) {
weight = Field(internal::linear_matroid_intersection_random());
}
return linear_matroid_intersection_size_with_weights(
first_vectors, second_vectors, weights);
}
} // namespace matroid
} // namespace m1une
#line 1 "matroid/matroid_intersection.hpp"
#include <algorithm>
#line 7 "matroid/matroid_intersection.hpp"
namespace m1une {
namespace matroid {
template <class IndependenceOracle1, class IndependenceOracle2>
std::vector<int> matroid_intersection(int ground_size, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2) {
assert(0 <= ground_size);
std::vector<char> selected(ground_size, false);
std::vector<int> elements;
std::vector<int> position(ground_size, -1);
while (true) {
std::vector<char> source(ground_size, false);
std::vector<char> sink(ground_size, false);
std::vector<int> distance(ground_size, -1);
std::vector<int> previous(ground_size, -1);
std::vector<int> queue;
queue.reserve(ground_size);
for (int x = 0; x < ground_size; x++) {
if (selected[x]) continue;
elements.push_back(x);
source[x] = oracle1(elements);
sink[x] = oracle2(elements);
elements.pop_back();
if (source[x]) {
distance[x] = 0;
queue.push_back(x);
}
}
int target = -1;
for (int head = 0; head < int(queue.size()) && target == -1; head++) {
int v = queue[head];
if (!selected[v] && sink[v]) {
target = v;
break;
}
if (selected[v]) {
int index = position[v];
assert(index != -1 && elements[index] == v);
for (int x = 0; x < ground_size; x++) {
if (selected[x] || distance[x] != -1) continue;
elements[index] = x;
bool independent = oracle1(elements);
elements[index] = v;
if (!independent) continue;
distance[x] = distance[v] + 1;
previous[x] = v;
queue.push_back(x);
}
} else {
for (int y : elements) {
if (distance[y] != -1) continue;
int index = position[y];
assert(index != -1 && elements[index] == y);
elements[index] = v;
bool independent = oracle2(elements);
elements[index] = y;
if (!independent) continue;
distance[y] = distance[v] + 1;
previous[y] = v;
queue.push_back(y);
}
}
}
if (target == -1) break;
for (int v = target; v != -1; v = previous[v]) selected[v] = !selected[v];
elements.clear();
std::fill(position.begin(), position.end(), -1);
for (int x = 0; x < ground_size; x++) {
if (!selected[x]) continue;
position[x] = int(elements.size());
elements.push_back(x);
}
#ifndef NDEBUG
assert(oracle1(elements));
assert(oracle2(elements));
#endif
}
return elements;
}
} // namespace matroid
} // namespace m1une
#line 1 "matroid/partition_matroid.hpp"
#line 8 "matroid/partition_matroid.hpp"
namespace m1une {
namespace matroid {
class PartitionMatroid {
private:
std::vector<int> _group;
std::vector<int> _capacity;
void validate() const {
#ifndef NDEBUG
for (int capacity : _capacity) assert(0 <= capacity);
for (int group : _group) assert(0 <= group && group < int(_capacity.size()));
#endif
}
public:
PartitionMatroid() = default;
explicit PartitionMatroid(std::vector<int> group) : _group(std::move(group)) {
int group_count = 0;
for (int value : _group) {
assert(0 <= value);
group_count = std::max(group_count, value + 1);
}
_capacity.assign(group_count, 1);
}
PartitionMatroid(std::vector<int> group, std::vector<int> capacity)
: _group(std::move(group)), _capacity(std::move(capacity)) {
validate();
}
int size() const {
return int(_group.size());
}
int group_count() const {
return int(_capacity.size());
}
const std::vector<int>& groups() const {
return _group;
}
const std::vector<int>& capacities() const {
return _capacity;
}
bool independent(const std::vector<int>& subset) const {
std::vector<int> count(_capacity.size(), 0);
for (int element : subset) {
assert(0 <= element && element < int(_group.size()));
int group = _group[element];
if (++count[group] > _capacity[group]) return false;
}
return true;
}
bool operator()(const std::vector<int>& subset) const {
return independent(subset);
}
};
} // namespace matroid
} // namespace m1une
#line 1 "matroid/uniform_matroid.hpp"
#line 6 "matroid/uniform_matroid.hpp"
namespace m1une {
namespace matroid {
class UniformMatroid {
private:
int _ground_size;
int _rank;
public:
UniformMatroid() : _ground_size(0), _rank(0) {}
UniformMatroid(int ground_size, int rank) : _ground_size(ground_size), _rank(rank) {
assert(0 <= rank && rank <= ground_size);
}
int size() const {
return _ground_size;
}
int rank() const {
return _rank;
}
bool independent(const std::vector<int>& subset) const {
return int(subset.size()) <= _rank;
}
bool operator()(const std::vector<int>& subset) const {
return independent(subset);
}
};
} // namespace matroid
} // namespace m1une
#line 1 "matroid/weighted_matroid_intersection.hpp"
#line 6 "matroid/weighted_matroid_intersection.hpp"
#include <queue>
#include <type_traits>
#line 10 "matroid/weighted_matroid_intersection.hpp"
namespace m1une {
namespace matroid {
template <class Weight>
struct WeightedMatroidIntersectionResult {
Weight total_weight = Weight(0);
std::vector<int> elements;
int size() const {
return int(elements.size());
}
bool empty() const {
return elements.empty();
}
};
namespace weighted_intersection_detail {
template <class Weight>
struct QueueGreater {
bool operator()(const std::pair<Weight, int>& lhs,
const std::pair<Weight, int>& rhs) const {
if (rhs.first < lhs.first) return true;
if (lhs.first < rhs.first) return false;
return lhs.second > rhs.second;
}
};
template <bool Maximize, class Weight>
Weight objective_cost(const Weight& change) {
if constexpr (Maximize) {
return Weight(0) - change;
} else {
return change;
}
}
template <bool Maximize, class Weight, class IndependenceOracle1, class IndependenceOracle2,
class OnSolution>
WeightedMatroidIntersectionResult<Weight> solve(
int ground_size, const std::vector<Weight>& weight, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2, OnSolution on_solution) {
static_assert(!std::is_arithmetic_v<Weight> || std::is_signed_v<Weight>,
"Weight must support negative intermediate values");
assert(0 <= ground_size);
assert(int(weight.size()) == ground_size);
const int source_vertex = ground_size;
const int sink_vertex = ground_size + 1;
const int vertex_count = ground_size + 2;
std::vector<char> selected(ground_size, false);
std::vector<int> elements;
std::vector<int> position(ground_size, -1);
std::vector<Weight> potential(vertex_count, Weight(0));
Weight total_weight = Weight(0);
on_solution(0, total_weight, elements);
while (true) {
std::vector<std::vector<int>> adjacency(vertex_count);
std::vector<int> sink_predecessors;
for (int x = 0; x < ground_size; x++) {
if (selected[x]) continue;
elements.push_back(x);
bool source = oracle1(elements);
bool sink = oracle2(elements);
elements.pop_back();
if (source) adjacency[source_vertex].push_back(x);
if (sink) {
adjacency[x].push_back(sink_vertex);
sink_predecessors.push_back(x);
}
}
for (int y : elements) {
int index = position[y];
assert(index != -1 && elements[index] == y);
for (int x = 0; x < ground_size; x++) {
if (selected[x]) continue;
elements[index] = x;
if (oracle1(elements)) adjacency[y].push_back(x);
if (oracle2(elements)) adjacency[x].push_back(y);
elements[index] = y;
}
}
if (adjacency[source_vertex].empty() || sink_predecessors.empty()) break;
auto vertex_length = [&](int vertex) {
if (vertex >= ground_size) return Weight(0);
Weight change = selected[vertex] ? Weight(0) - weight[vertex] : weight[vertex];
return objective_cost<Maximize>(change);
};
auto reduced_length = [&](int from, int to) {
return vertex_length(to) - potential[to] + potential[from];
};
int first_source = adjacency[source_vertex].front();
potential[source_vertex] = potential[first_source] - vertex_length(first_source);
for (int x : adjacency[source_vertex]) {
Weight candidate = potential[x] - vertex_length(x);
if (potential[source_vertex] < candidate) potential[source_vertex] = candidate;
}
potential[sink_vertex] = potential[sink_predecessors.front()];
for (int x : sink_predecessors) {
if (potential[x] < potential[sink_vertex]) potential[sink_vertex] = potential[x];
}
Weight source_potential = potential[source_vertex];
for (Weight& value : potential) value = value - source_potential;
#ifndef NDEBUG
for (int from = 0; from < vertex_count; from++) {
for (int to : adjacency[from]) assert(!(reduced_length(from, to) < Weight(0)));
}
#endif
// Dijkstra is performed lazily: fixed_distance is added to every
// not-yet-fixed potential at once, then materialized when a vertex is fixed.
using QueueEntry = std::pair<Weight, int>;
std::priority_queue<QueueEntry, std::vector<QueueEntry>, QueueGreater<Weight>> heap;
std::vector<char> fixed(vertex_count, false);
std::vector<char> has_distance(vertex_count, false);
std::vector<Weight> distance(vertex_count, Weight(0));
std::vector<int> previous(vertex_count, -1);
heap.push({Weight(0), source_vertex});
has_distance[source_vertex] = true;
Weight fixed_distance = Weight(0);
bool reached_sink = false;
std::vector<int> tight_stack;
tight_stack.reserve(vertex_count);
while (!heap.empty() && !reached_sink) {
int start = heap.top().second;
heap.pop();
if (fixed[start]) continue;
if (start != source_vertex) {
assert(previous[start] != -1);
fixed_distance = reduced_length(previous[start], start);
}
tight_stack.clear();
fixed[start] = true;
potential[start] = potential[start] + fixed_distance;
tight_stack.push_back(start);
while (!tight_stack.empty() && !reached_sink) {
int current = tight_stack.back();
tight_stack.pop_back();
if (current == sink_vertex) {
reached_sink = true;
break;
}
for (int next : adjacency[current]) {
if (fixed[next]) continue;
Weight slack = reduced_length(current, next) - fixed_distance;
assert(!(slack < Weight(0)));
if (!(Weight(0) < slack)) {
previous[next] = current;
fixed[next] = true;
potential[next] = potential[next] + fixed_distance;
tight_stack.push_back(next);
} else {
Weight candidate = fixed_distance + slack;
if (!has_distance[next] || candidate < distance[next]) {
has_distance[next] = true;
distance[next] = candidate;
previous[next] = current;
heap.push({candidate, next});
}
}
}
}
}
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (!fixed[vertex]) potential[vertex] = potential[vertex] + fixed_distance;
}
if (!reached_sink) break;
std::fill(previous.begin(), previous.end(), -1);
std::vector<char> reached(vertex_count, false);
std::vector<int> queue;
queue.reserve(vertex_count);
reached[source_vertex] = true;
queue.push_back(source_vertex);
for (int head = 0; head < int(queue.size()) && !reached[sink_vertex]; head++) {
int current = queue[head];
for (int next : adjacency[current]) {
if (reached[next]) continue;
Weight length = reduced_length(current, next);
assert(!(length < Weight(0)));
if (Weight(0) < length) continue;
reached[next] = true;
previous[next] = current;
queue.push_back(next);
}
}
assert(reached[sink_vertex]);
if (!reached[sink_vertex]) break;
// A shortest tight path with the fewest edges preserves the potential invariant
// after its elements switch between the inside and outside of the solution.
for (int v = sink_vertex; v != source_vertex; v = previous[v]) {
assert(v != -1);
if (v < ground_size) {
potential[v] = potential[v] - vertex_length(v);
if (selected[v]) {
total_weight = total_weight - weight[v];
} else {
total_weight = total_weight + weight[v];
}
selected[v] = !selected[v];
}
}
elements.clear();
std::fill(position.begin(), position.end(), -1);
for (int x = 0; x < ground_size; x++) {
if (!selected[x]) continue;
position[x] = int(elements.size());
elements.push_back(x);
}
#ifndef NDEBUG
assert(oracle1(elements));
assert(oracle2(elements));
#endif
on_solution(int(elements.size()), total_weight, elements);
}
WeightedMatroidIntersectionResult<Weight> result;
result.elements = elements;
result.total_weight = total_weight;
return result;
}
} // namespace weighted_intersection_detail
template <class Weight, class IndependenceOracle1, class IndependenceOracle2>
WeightedMatroidIntersectionResult<Weight> weighted_matroid_intersection_max(
int ground_size, const std::vector<Weight>& weight, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2) {
auto ignore = [](int, const Weight&, const std::vector<int>&) {};
return weighted_intersection_detail::solve<true>(ground_size, weight, oracle1, oracle2,
ignore);
}
template <class Weight, class IndependenceOracle1, class IndependenceOracle2>
WeightedMatroidIntersectionResult<Weight> weighted_matroid_intersection_min(
int ground_size, const std::vector<Weight>& weight, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2) {
auto ignore = [](int, const Weight&, const std::vector<int>&) {};
return weighted_intersection_detail::solve<false>(ground_size, weight, oracle1, oracle2,
ignore);
}
template <class Weight, class IndependenceOracle1, class IndependenceOracle2, class OnSolution>
WeightedMatroidIntersectionResult<Weight> weighted_matroid_intersection_max_each(
int ground_size, const std::vector<Weight>& weight, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2, OnSolution on_solution) {
return weighted_intersection_detail::solve<true>(ground_size, weight, oracle1, oracle2,
on_solution);
}
template <class Weight, class IndependenceOracle1, class IndependenceOracle2, class OnSolution>
WeightedMatroidIntersectionResult<Weight> weighted_matroid_intersection_min_each(
int ground_size, const std::vector<Weight>& weight, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2, OnSolution on_solution) {
return weighted_intersection_detail::solve<false>(ground_size, weight, oracle1, oracle2,
on_solution);
}
template <class Weight, class IndependenceOracle1, class IndependenceOracle2>
WeightedMatroidIntersectionResult<Weight> weighted_matroid_intersection(
int ground_size, const std::vector<Weight>& weight, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2) {
return weighted_matroid_intersection_max(ground_size, weight, oracle1, oracle2);
}
} // namespace matroid
} // namespace m1une
#line 11 "matroid/all.hpp"