3736번: System Engineer

https://www.acmicpc.net/problem/3736

이분 매칭 문제이다. Hopcroft–Karp Algorithm 알고리즘을 써야 TLE를 피할 수 있다.

시간복잡도는 $O(n^{2.5})$

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> adj[10000];
int n, ck[10000], rev[10000], lv[10000];
bool BFS() {
    queue<int> q;
    fill(lv, lv + n, -1);
    for (int i = 0; i < n; i++) if (!ck[i]) q.push(i), lv[i] = 0;
    int flag = 0;
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (int it : adj[h]) {
            if (!~rev[it]) flag = 1;
            else if (!~lv[rev[it]]) lv[rev[it]] = lv[h] + 1, q.push(rev[it]);
        }
    }
    return flag;
}
int DFS(int h) {
    for (int it : adj[h]) if (!~rev[it] || lv[h] < lv[rev[it]] && DFS(rev[it])) {
        rev[it] = h;
        return 1;
    }
    lv[h] = 0;
    return 0;
}
int main() {
    while (~scanf("%d", &n)) {
        int r = 0;
        for (int i = 0, x, m, y; i < n; i++) {
            scanf("%d: (%d)", &x, &m);
            adj[x].clear();
            for (int j = 0; j < m; j++) scanf("%d", &y), adj[x].push_back(y - n);
        }
        fill(rev, rev + n, -1);
        fill(ck, ck + n, 0);
        while (BFS()) {
            for (int i = 0; i < n; i++) if (!lv[i] && DFS(i)) ck[i] = 1, r++;
        }
        printf("%d\n", r);
    }
    return 0;
}