cplib-cpp

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

View the Project on GitHub hitonanode/cplib-cpp

:warning: Matroid union （マトロイドの合併）
(combinatorial_opt/matroid_union.hpp)

2つのマトロイド $M_{1} = (E, \mathcal{I}_{1}), M_{2} = (E, \mathcal{I}_{2})$, $\mathcal{I}_{1}$ に関して独立な集合 $I_1$, $\mathcal{I}_{2}$ に関して独立な集合 $I_2$ で $I_1 \cap I_2 = \emptyset$ を満たすものが与えられたとき，$I’_1 + I’_2 = I_1 + I_2 + \{ e \}$ を満たす新たな排反な独立集合 $I’_1, I’_2$ を見つけるアルゴリズム．特に重み最小の $e$ から貪欲に追加を試すことで，「合併したマトロイド」の最小重みサイズ $k$ 独立集合が $k = 1, 2, \dots$ について順次求められる．

これを応用すると，与えられた重み付き無向グラフについて，辺素な二つの全域木であって重みの総和が最小なものを見つけることも可能．

アルゴリズムの概要

$|E| = n$ として，各要素 $e \in E$ に終点 $t$ を加えた $n + 1$ 頂点の有向グラフに次の要領で辺を張る．すべての辺は重みなしとする．

辺を逆向きにしたグラフで $t$ から BFS を行い，各要素から $t$ への最短路を求める．$e \notin I_1 \cup I_2$ で $t$ に到達可能な要素のうち，重み $w(e)$ が最小のものを追加する．このとき重みと交換回数は足し合わせず，まず追加要素の重みを最小化し，その要素からの交換回数を最小化する．該当する要素がなければ $I_1 \cup I_2$ は既に合併したマトロイド上の最大独立集合である．

選んだ $e$ から $t$ への最短路上で，要素を $I_1$ と $I_2$ の間で移動させる．最短路を使うことで独立性が保たれ，合併集合には $e$ だけが新たに加わる．重みを省略した場合は，追加可能ないずれかの要素を選ぶ．

本コードには実装されていないが，3 個以上のマトロイドの合併に対しても同様のアルゴリズムが適用可能である．

使用方法

問題例

参考文献・リンク

Code

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

// CUT begin
// Union matroid augment
// From I1, I2 (independent, exclusive),
// - find I1' and I2' s.t. |I1'| + |I2'| = |I1| + |I2| + 1 and return true
// - or return false
// Complexity: O(n(c + r)) (r: current rank, c: circuit query)
// Algorithm based on https://math.mit.edu/~goemans/18438F09/lec13.pdf
// Verified: CodeChef HAMEL
template <class M1, class M2, class State1, class State2, class T = int>
bool augment_union_matroid(M1 &matroid1, M2 &matroid2, State1 &I1, State2 &I2,
                           const std::vector<T> &weights) {
    const int M = matroid1.size();
    const int gt = M;
    std::vector<std::vector<int>> rev(M + 1);
    std::vector<int> color(M, -1);
    matroid1.set(I1);
    matroid2.set(I2);
    for (int e = 0; e < M; e++) {
        if (!I1[e]) {
            auto c = matroid1.circuit(e);
            if (c.empty()) rev[gt].push_back(e), color[e] = 0;
            for (int f : c) {
                if (f != e) rev[f].push_back(e);
            }
        }
        if (!I2[e]) {
            auto c = matroid2.circuit(e);
            if (c.empty()) rev[gt].push_back(e), color[e] = 1;
            for (int f : c) {
                if (f != e) rev[f].push_back(e);
            }
        }
    }
    // Find a shortest exchange path to gt from every augmentable element.
    std::vector<int> next(M + 1, -1), q{gt};
    next[gt] = gt;
    for (int i = 0; i < int(q.size()); ++i) {
        for (int e : rev[q[i]]) {
            if (next[e] >= 0) continue;
            next[e] = q[i];
            q.push_back(e);
        }
    }

    // Minimize the added weight independently of the number of exchanges.
    int start = -1;
    for (int e = 0; e < M; ++e) {
        if (I1[e] or I2[e] or next[e] < 0) continue;
        if (start < 0 or (!weights.empty() and weights[e] < weights[start])) start = e;
    }
    if (start < 0) return false;

    std::vector<int> aug_path;
    for (int e = start; e != gt; e = next[e]) aug_path.push_back(e);
    int c0 = -1;
    if (I1[aug_path.back()]) c0 = 1;
    if (I2[aug_path.back()]) c0 = 0;
    if (c0 < 0) c0 = color[aug_path.back()];
    for (int k = int(aug_path.size()) - 1; k >= 0; --k) {
        int e = aug_path[k];
        (c0 ? I2 : I1)[e] = 1, (c0 ? I1 : I2)[e] = 0;
        c0 ^= 1;
    }
    return true;
}

// (Min weight) matroid partition
template <class M1, class M2, class T = int>
std::pair<std::vector<bool>, std::vector<bool>>
MinWeightMaxIndepSetInUnionMatroid(M1 mat1, M2 mat2, const std::vector<T> &weights = {}) {
    using State = std::vector<bool>;
    assert(mat1.size() == mat2.size());
    const int M = mat1.size();
    State I1(M), I2(M);
    while (augment_union_matroid(mat1, mat2, I1, I2, weights)) {}
    return {I1, I2};
}
#line 2 "combinatorial_opt/matroid_union.hpp"
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// Union matroid augment
// From I1, I2 (independent, exclusive),
// - find I1' and I2' s.t. |I1'| + |I2'| = |I1| + |I2| + 1 and return true
// - or return false
// Complexity: O(n(c + r)) (r: current rank, c: circuit query)
// Algorithm based on https://math.mit.edu/~goemans/18438F09/lec13.pdf
// Verified: CodeChef HAMEL
template <class M1, class M2, class State1, class State2, class T = int>
bool augment_union_matroid(M1 &matroid1, M2 &matroid2, State1 &I1, State2 &I2,
                           const std::vector<T> &weights) {
    const int M = matroid1.size();
    const int gt = M;
    std::vector<std::vector<int>> rev(M + 1);
    std::vector<int> color(M, -1);
    matroid1.set(I1);
    matroid2.set(I2);
    for (int e = 0; e < M; e++) {
        if (!I1[e]) {
            auto c = matroid1.circuit(e);
            if (c.empty()) rev[gt].push_back(e), color[e] = 0;
            for (int f : c) {
                if (f != e) rev[f].push_back(e);
            }
        }
        if (!I2[e]) {
            auto c = matroid2.circuit(e);
            if (c.empty()) rev[gt].push_back(e), color[e] = 1;
            for (int f : c) {
                if (f != e) rev[f].push_back(e);
            }
        }
    }
    // Find a shortest exchange path to gt from every augmentable element.
    std::vector<int> next(M + 1, -1), q{gt};
    next[gt] = gt;
    for (int i = 0; i < int(q.size()); ++i) {
        for (int e : rev[q[i]]) {
            if (next[e] >= 0) continue;
            next[e] = q[i];
            q.push_back(e);
        }
    }

    // Minimize the added weight independently of the number of exchanges.
    int start = -1;
    for (int e = 0; e < M; ++e) {
        if (I1[e] or I2[e] or next[e] < 0) continue;
        if (start < 0 or (!weights.empty() and weights[e] < weights[start])) start = e;
    }
    if (start < 0) return false;

    std::vector<int> aug_path;
    for (int e = start; e != gt; e = next[e]) aug_path.push_back(e);
    int c0 = -1;
    if (I1[aug_path.back()]) c0 = 1;
    if (I2[aug_path.back()]) c0 = 0;
    if (c0 < 0) c0 = color[aug_path.back()];
    for (int k = int(aug_path.size()) - 1; k >= 0; --k) {
        int e = aug_path[k];
        (c0 ? I2 : I1)[e] = 1, (c0 ? I1 : I2)[e] = 0;
        c0 ^= 1;
    }
    return true;
}

// (Min weight) matroid partition
template <class M1, class M2, class T = int>
std::pair<std::vector<bool>, std::vector<bool>>
MinWeightMaxIndepSetInUnionMatroid(M1 mat1, M2 mat2, const std::vector<T> &weights = {}) {
    using State = std::vector<bool>;
    assert(mat1.size() == mat2.size());
    const int M = mat1.size();
    State I1(M), I2(M);
    while (augment_union_matroid(mat1, mat2, I1, I2, weights)) {}
    return {I1, I2};
}
Back to top page