BOJ)3736 System Engineer

문제: icpc.me/3736

작업 세트와 서버로 이루어진 이분 그래프에서 최대 매칭을 구하는 문제이다.

정점의 개수가 10000개 이므로 일반 이분 매칭 소스로는 TLE가 나므로 hopcroft-karp 알고리즘을 이용하여 최대매칭을 구해줘야 한다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
struct hopcroft_karp {
    int n;
    vector<int> a, b, dist, match, work;
    vector<vector<int>> vt;
    hopcroft_karp(int n) :n(n) {
        a.assign(n + 1, -1);
        b.assign(n + 1, -1);
        dist.assign(n + 1, 0);
        match.assign(n + 1, 0);
        vt.resize(n + 1);
    }
    void addEdge(int x, int y) {
        vt[x].push_back(y);
    }
    void bfs() {
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
            if (!match[i]) {
                dist[i] = 0;
                qu.push(i);
            }
            else
                dist[i] = INF;
        }
        while (qu.size()) {
            int here = qu.front();
            qu.pop();
            for (auto there : vt[here]) {
                if (b[there] != -1 && dist[b[there]] == INF) {
                    dist[b[there]] = dist[here] + 1;
                    qu.push(b[there]);
                }
            }
        }
    }
    bool dfs(int here) {
        for (int &i = work[here]; i < vt[here].size(); i++) {
            int there = vt[here][i];
            if (b[there] == -1 || dist[b[there]] == dist[here] + 1 && dfs(b[there])) {
                match[here] = true;
                a[here] = there;
                b[there] = here;
                return true;
            }
        }
        return false;
    }
    int solve() {
        int ret = 0;
        while (1) {
            work.assign(n + 1, 0);
            bfs();
            int flow = 0;
            for (int i = 1; i <= n; i++)
                if (!match[i] && dfs(i))flow++;
            if (!flow)break;
            ret += flow;
        }
        return ret;
    }
};
int n, m, x, y;
int main() {
    while (scanf("%d", &n) != EOF) {
        hopcroft_karp hk(n);
        for (int i = 0; i < n; i++) {
            scanf("%d: (%d)", &x, &m);
            for (int j = 0; j < m; j++) {
                scanf("%d", &y);
                hk.addEdge(x + 1, y - n + 1);
            }
        }
        printf("%d\n", hk.solve());
    }
    return 0;
}