結果

問題 No.3024 全単射的
ユーザー Today03
提出日時 2025-02-15 03:07:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 503 ms / 5,000 ms
コード長 2,822 bytes
コンパイル時間 3,988 ms
コンパイル使用メモリ 302,040 KB
実行使用メモリ 35,272 KB
最終ジャッジ日時 2025-02-15 03:07:16
合計ジャッジ時間 7,698 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;
template <typename Cap>
struct MaxFlow {
    MaxFlow() = default;
    MaxFlow(int n) {
        this->n = n;
        graph = vector<vector<tuple<int, int, Cap>>>(n);
    }
    void add_edge(int u, int v, Cap c) {
        graph[u].push_back(make_tuple(v, graph[v].size(), c));
        graph[v].push_back(make_tuple(u, (int)graph[u].size() - 1, 0));
    }
    Cap get(int start, int goal) {
        Cap ret = 0;
        while (true) {
            vector<int> dst = calculate_distance(start);
            if (dst[goal] < 0) return ret;
            vector<int> removed(n, 0);
            while (true) {
                Cap add = flowing(start, goal, numeric_limits<Cap>::max(), removed, dst);
                if (add == 0) break;
                ret += add;
            }
        }
        return ret;
    }
private:
    int n;
    vector<vector<tuple<int, int, Cap>>> graph;
    vector<int> calculate_distance(int start) {
        vector<int> dst(n, -1);
        dst[start] = 0;
        queue<int> que;
        que.push(start);
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (auto [nxt, _, cap] : graph[now]) {
                if (cap > 0 && dst[nxt] == -1) {
                    dst[nxt] = dst[now] + 1;
                    que.push(nxt);
                }
            }
        }
        return dst;
    }
    Cap flowing(int now, int goal, Cap limit, vector<int> &removed, vector<int> &dst) {
        if (now == goal) {
            return limit;
        }
        while (removed[now] < (int)graph[now].size()) {
            auto [nxt, rev, cap] = graph[now][removed[now]];
            if (cap > 0 && dst[now] < dst[nxt]) {
                Cap flow = flowing(nxt, goal, min(limit, cap), removed, dst);
                if (flow > 0) {
                    std::get<2>(graph[now][removed[now]]) -= flow;
                    std::get<2>(graph[nxt][rev]) += flow;
                    return flow;
                }
            }
            removed[now]++;
        }
        return 0;
    }
};
int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> X(N), Y(N), V;
    for (int i = 0; i < N; i++) cin >> X[i] >> Y[i], V.push_back(X[i]), V.push_back(Y[i]);
    ranges::sort(V);
    V.erase(unique(V.begin(), V.end()), V.end());
    auto get = [&](ll x) { return ranges::lower_bound(V, x) - V.begin(); };
    int S = ssize(V);
    int T = N + S + 2, s = N + S, t = N + S + 1;
    MaxFlow<int> mf(T);
    for (int i = 0; i < N; i++) mf.add_edge(s, i, 1);
    for (int i = N; i < N + S; i++) mf.add_edge(i, t, 1);
    for (int i = 0; i < N; i++) mf.add_edge(i, N + get(X[i]), 1), mf.add_edge(i, N + get(Y[i]), 1);
    cout << mf.get(s, t) << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0