:heavy_check_mark: test/AOJ/GRL_7_A.test.cpp

Depends on

Code

#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#include <bits/stdc++.h>

#include "library/graph/matching/BipartiteMatching.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x, y, m;
    std::cin >> x >> y >> m;

    BipartiteMatching BM(x, y);
    while (m--) {
        int u, v;
        std::cin >> u >> v;
        BM.add_edge(u, v);
    }
    std::cout << BM.solve().size() << std::endl;
}
#line 1 "test/AOJ/GRL_7_A.test.cpp"
#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#include <bits/stdc++.h>

#line 2 "library/graph/matching/BipartiteMatching.hpp"

// 重み無し
#line 2 "library/flow/Dinic.hpp"

// https://misawa.github.io/others/flow/dinic_time_complexity.html
#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
    WeightedEdge() = default;
    WeightedEdge(int from, int to, T weight)
        : from(from), to(to), weight(weight) {}
    int from, to;
    T weight;
    operator int() const { return to; }
};

template <typename T> struct WeightedGraph {
    int n;
    using weight_type = T;
    using edge_type = WeightedEdge<T>;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        WeightedGraph *g;
        int l, r;

      public:
        OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const WeightedGraph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
            : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
    WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to, T weight) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to, weight);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v, T weight) {
        add_arc(u, v, weight);
        add_arc(v, u, weight);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            T weight;
            std::cin >> weight;
            if (directed)
                add_arc(u, v, weight);
            else
                add_edge(u, v, weight);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __DEBUG
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << "(" << edges[i].to << "," << edges[i].weight
                          << ")";
            std::cerr << "\n";
        }
    }
};
#line 5 "library/flow/Dinic.hpp"
template <typename T> class Dinic {
    struct EdgeInfo {
        T cap;
        int rev;
    };
    WeightedGraph<EdgeInfo> G;
    std::vector<int> level, current_edge, out_deg;
    int s, t;
    std::vector<std::pair<int, int>> edge_memo;

    std::queue<int> que;
    void bfs() {
        // level[v]を（容量正の辺による）sからの最短距離にする
        // 到達出来なければ-1
        std::ranges::fill(level, -1);
        level[s] = 0;
        que.emplace(s);
        while (que.size()) {
            int v = que.front();
            que.pop();
            for (const auto &e : G[v]) {
                const auto &[cap, rev] = e.weight;
                if (cap == 0 || ~level[e.to])
                    continue;
                level[e.to] = level[v] + 1;
                que.emplace(e.to);
            }
        }
    }
    T dfs(int v, T f) {
        // vからtに最短路で水を流す fがvまで持ってこれた水量 流せた量が返り値
        if (v == t)
            return f;
        for (int &i = current_edge[v]; i < G[v].size();
             i++) { // このdfsで使わなかった辺は次のBFSまで使われることはない
            auto &e = G[v][i];
            auto &[cap, rev] = e.weight;
            if (cap > 0 &&
                level[v] <
                    level
                        [e.to]) { // bfsをしているのでlevel[v]<level[e.to]ならlevel[v]+1==level[e.to]
                T d = dfs(e.to, std::min(f, cap));
                if (d == 0)
                    continue;
                cap -= d;
                G[e.to][rev].weight.cap += d;
                return d; // 一本流せたらreturn
            }
        }
        return 0;
    }

  public:
    Dinic() = default;
    Dinic(int n, int s = 0, int t_ = -1)
        : G(n), level(n), current_edge(n), out_deg(n, 0), s(s), t(t_) {
        if (t < 0)
            t = n - 1;
    }

    // 0-indexed で edge_id 番目に追加した辺に流した量を返す
    T operator[](const int edge_id) const {
        assert(G.is_prepared());
        const auto &[from, id] = edge_memo[edge_id];
        return G.edge[from][id].weight.cap;
    }
    // 辺を追加した順番に [from,to,流量]
    std::vector<std::tuple<int, int, T>> all_edge() {
        assert(G.is_prepared());
        std::vector<std::tuple<int, int, T>> res;
        res.reserve(edge_memo.size());
        for (const auto &[v, id] : edge_memo) {
            const auto &[to, from, weight] = G[v][id];
            res.emplace_back(from, to, weight.cap);
        }
        return res;
    }

    void add_arc(int from, int to, T cap) {
        G.add_arc(from, to, {cap, out_deg[to]});
        G.add_arc(to, from, {0, out_deg[from]++});
        edge_memo.emplace_back(to, out_deg[to]++);
    }
    T flow(T lim = std::numeric_limits<T>::max() / 2) {
        if (!G.is_prepared())
            G.build();
        T fl = 0;
        while (lim > 0) {
            bfs();
            if (level[t] < 0)
                break;
            std::ranges::fill(current_edge, 0);
            while (true) {
                T f = dfs(s, lim);
                if (f == 0)
                    break;
                fl += f;
                lim -= f;
            }
        }
        return fl;
    }

    T st_flow(int s_, int t_, T lim = std::numeric_limits<T>::max() / 2) {
        s = s_;
        t = t_;
        return flow(lim);
    }
};
#line 5 "library/graph/matching/BipartiteMatching.hpp"
class BipartiteMatching {
    int A, B; // 左右の頂点数
    int S, T;
    Dinic<int> fl;

  public:
    BipartiteMatching(int A, int B)
        : A(A), B(B), S(A + B), T(A + B + 1), fl(A + B + 2, S, T) {
        for (int i = 0; i < A; i++)
            fl.add_arc(S, i, 1);
        for (int j = 0; j < B; j++)
            fl.add_arc(A + j, T, 1);
    }
    void add_edge(int u, int v) {
        assert(0 <= u and u < A);
        assert(0 <= v and v < B);
        fl.add_arc(u, A + v, 1);
    }
    std::vector<std::pair<int, int>> solve() {
        int K = fl.flow(std::min(A, B));
        std::vector<std::pair<int, int>> res;
        res.reserve(K);
        auto all_edge = fl.all_edge();
        for (int i = A + B; i < all_edge.size(); i++) {
            const auto &[from, to, flow] = all_edge[i];
            if (flow)
                res.emplace_back(from, to - A);
        }
        return res;
    }
};
#line 6 "test/AOJ/GRL_7_A.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x, y, m;
    std::cin >> x >> y >> m;

    BipartiteMatching BM(x, y);
    while (m--) {
        int u, v;
        std::cin >> u >> v;
        BM.add_edge(u, v);
    }
    std::cout << BM.solve().size() << std::endl;
}
Back to top page