src/watashi/bimatch.hpp

• View this file on GitHub
• Last update: 2025-02-17 23:08:47+08:00
• Include: #include "src/watashi/bimatch.hpp"

Code

// maximum matchings in bipartite graphs
// maximum cardinality bipartite matching
// O(|V||E|), generally fast

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

struct Hungarian {
    int nx, ny;
    vector<int> mx, my;
    vector<vector<int>> e;

    void init(int nx, int ny) {
        this->nx = nx;
        this->ny = ny;
        mx.resize(nx);
        my.resize(ny);
        e.clear();
        e.resize(nx);
        mark.resize(nx);
    }

    void add(int a, int b) {
        e[a].push_back(b);
    }

    // vector<bool> is evil!!!
    basic_string<bool> mark;

    bool augment(int i) {
        if (!mark[i]) {
            mark[i] = true;
            for (vector<int>::const_iterator j = e[i].begin(); j != e[i].end(); ++j) {
                if (my[*j] == -1 || augment(my[*j])) {
                    mx[i] = *j;
                    my[*j] = i;
                    return true;
                }
            }
        }
        return false;
    }

    int gao() {
        int ret = 0;
        fill(mx.begin(), mx.end(), -1);
        fill(my.begin(), my.end(), -1);
        for (int i = 0; i < nx; ++i) {
            fill(mark.begin(), mark.end(), false);
            if (augment(i)) {
                ++ret;
            }
        }
        return ret;
    }
};

#line 1 "src/watashi/bimatch.hpp"
// maximum matchings in bipartite graphs
// maximum cardinality bipartite matching
// O(|V||E|), generally fast

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

struct Hungarian {
    int nx, ny;
    vector<int> mx, my;
    vector<vector<int>> e;

    void init(int nx, int ny) {
        this->nx = nx;
        this->ny = ny;
        mx.resize(nx);
        my.resize(ny);
        e.clear();
        e.resize(nx);
        mark.resize(nx);
    }

    void add(int a, int b) {
        e[a].push_back(b);
    }

    // vector<bool> is evil!!!
    basic_string<bool> mark;

    bool augment(int i) {
        if (!mark[i]) {
            mark[i] = true;
            for (vector<int>::const_iterator j = e[i].begin(); j != e[i].end(); ++j) {
                if (my[*j] == -1 || augment(my[*j])) {
                    mx[i] = *j;
                    my[*j] = i;
                    return true;
                }
            }
        }
        return false;
    }

    int gao() {
        int ret = 0;
        fill(mx.begin(), mx.end(), -1);
        fill(my.begin(), my.end(), -1);
        for (int i = 0; i < nx; ++i) {
            fill(mark.begin(), mark.end(), false);
            if (augment(i)) {
                ++ret;
            }
        }
        return ret;
    }
};

Back to top page