結果

問題 No.1703 Much Matching
ユーザー atreeatree
提出日時 2021-10-08 23:21:27
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,051 bytes
コンパイル時間 2,565 ms
コンパイル使用メモリ 223,884 KB
実行使用メモリ 73,600 KB
最終ジャッジ日時 2024-07-23 07:17:44
合計ジャッジ時間 11,690 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 AC 4 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "E.cpp"
#include <bits/stdc++.h>
using namespace std;
#define overload3(_NULL, _1, _2, name, ...) name
#define rep1(i, n) for (remove_const_t<remove_reference_t<decltype(n)>> i = 0; i < (n); i++)
#define rep2(i, a, b) for (remove_const_t<remove_reference_t<decltype(b)>> i = a; i < (b); i++)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#if __has_include(<debug.hpp>)
#    include <debug.hpp>
#else
#    define dbg(...) (void(0))
#endif
template<class T> void drop(const T &x) {
    cout << x << "\n";
    exit(0);
}
template<class T> bool chmax(T &a, const T &b) { return a < b and (a = b, true); }
template<class T> bool chmin(T &a, const T &b) { return a > b and (a = b, true); }
using i64 = long long;
using usize = size_t;

using Flow = pair<int, vector<vector<usize>>>;

#line 2 "/Users/atree/src/compete-cpp/competitive-library/lib/graph/ford_fulkerson.hpp"

#line 5 "/Users/atree/src/compete-cpp/competitive-library/lib/graph/ford_fulkerson.hpp"

struct FordFulkerson {
    using size_t = std::size_t;
    using flow_t = int;

  private:
    struct Edge {
        size_t to, from, rev_ind;
        flow_t cap;
        Edge(size_t to, size_t from, size_t rev_ind, flow_t cap): to(to), from(from), rev_ind(rev_ind), cap(cap) {}
    };
    std::vector<std::vector<Edge>> data;
    Edge &rev(const Edge &e) { return data[e.to][e.rev_ind]; }
    void run_flow(Edge &e, flow_t f) {
        e.cap -= f;
        rev(e).cap += f;
    }
    flow_t find(const size_t &v, const size_t &t, const flow_t &f, std::vector<bool> &seen, vector<usize> &path) {
        if (v == t) return f;
        seen[v] = true;
        for (auto &&e: data[v]) {
            if (seen[e.to] or e.cap <= 0) continue;
            flow_t flow = find(e.to, t, std::min(f, e.cap), seen, path);
            if (flow == 0) continue;
            path.push_back(e.to);
            run_flow(e, flow);
            return flow;
        }
        return 0;
    }

  public:
    explicit FordFulkerson(const size_t n = 0): data(n) {}
    [[nodiscard]] size_t size() const { return std::size(data); }
    std::vector<Edge> &operator[](size_t i) { return data[i]; }
    void add_edge(size_t from, size_t to, flow_t cap) {
        size_t reg_ind = data[from].size();
        size_t rev_ind = data[to].size();
        data[from].emplace_back(Edge{ to, from, rev_ind, cap });
        data[to].emplace_back(Edge{ from, to, reg_ind, 0 });
    }
    Flow max_flow(size_t s, size_t t) {
        flow_t res = 0;
        vector<vector<usize>> g{};
        while (true) {
            std::vector<bool> seen(data.size(), false);
            vector<usize> path{};
            flow_t flow = find(s, t, std::numeric_limits<int>::max(), seen, path);
            if (flow == 0) return { res, g };
            res += flow;
            g.emplace_back(path);
        }
    }
};
#line 22 "E.cpp"

int main() {
    usize n, m, q;
    cin >> n >> m >> q;
    auto graph = FordFulkerson(n + m + 2);
    rep(i, n) graph.add_edge(0, i + 1, 1);
    rep(i, m) graph.add_edge(n + i + 1, n + m + 1, 1);
    rep(_, q) {
        usize a, b;
        cin >> a >> b;
        graph.add_edge(a, n + b, 1);
    }
    const auto [f, matching] = graph.max_flow(0, n + m + 1);
    dbg(matching);
    vector<pair<usize, usize>> pairs{};
    for (const auto &v: matching) {
        assert(size(v) == 3);
        pairs.emplace_back(v[2], v[1]);
    }
    sort(begin(pairs), end(pairs));
    vector<usize> t{};
    transform(begin(pairs), end(pairs), back_inserter(t), [](const auto &p) { return p.second; });
    const usize INF = numeric_limits<usize>::max();
    vector<usize> dp(size(t), INF);
    rep(i, size(t)) {
        auto it = upper_bound(dp.begin(), dp.end(), t[i]);
        *it = t[i];
    }
    cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin() << "\n";
}

struct IOSetup {
    IOSetup() noexcept {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << std::fixed << std::setprecision(10);
        cerr << std::fixed << std::setprecision(10);
    }
} iosetup;
0