結果

問題 No.3024 全単射的
ユーザー Today03
提出日時 2025-02-15 03:10:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,964 bytes
コンパイル時間 3,662 ms
コンパイル使用メモリ 296,520 KB
実行使用メモリ 21,408 KB
最終ジャッジ日時 2025-02-15 03:11:05
合計ジャッジ時間 14,495 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

// O(nm)
vector<pair<int, int>> bipartiteMatching(const vector<vector<int>>& g) {
    int n = g.size();
    vector<int> match(n, -1);
    vector<bool> used(n);

    auto dfs = [&](auto dfs, int now) -> bool {
        used[now] = true;
        for (int nxt : g[now]) {
            if (match[nxt] == -1 || !used[match[nxt]] && dfs(dfs, match[nxt])) {
                match[now] = nxt;
                match[nxt] = now;
                return true;
            }
        }
        return false;
    };

    for (int i = 0; i < n; i++) {
        if (match[i] == -1) {
            fill(used.begin(), used.end(), false);
            dfs(dfs, i);
        }
    }

    vector<pair<int, int>> ret;
    for (int i = 0; i < n; i++) {
        if (match[i] > i && match[match[i]] == i) ret.push_back({i, match[i]});
    }
    return ret;
}

struct BiInfo {
    int max_matching, min_edge_cover, max_independent_set, min_vertex_cover;
};

BiInfo biInfo(const vector<vector<int>>& g) {
    int n = g.size();
    int isolation = 0;
    for (int i = 0; i < n; i++)
        if ((int)g[i].size() == 0) isolation++;

    BiInfo ret;
    int m = bipartiteMatching(g).size();
    ret.max_matching = m;
    ret.min_edge_cover = isolation == 0 ? n - m : -1;
    ret.min_vertex_cover = m;
    ret.max_independent_set = n - m;

    return ret;
}

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;
    vector<vector<int>> G(T);
    for (int i = 0; i < N; i++) G[i].push_back(N + get(X[i])), G[i].push_back(N + get(Y[i]));

    cout << biInfo(G).max_matching << endl;
}
0