[C++] 열혈강호 (백준 11375번) - 이분 매칭

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

 

각 직원은 하나의 일만 담당할 수 있고, 각각의 일을 담당하는 사람은 한명이어야 한다.

⇒ 한 쪽에는 직원 노드들이 있고 한 쪽에는 일 노드들이 있을 때, 담당 가능한 직원-일에 대해서 간선을 이어주면 이분 그래프가 만들어진다. 이 이분 그래프에서 최대 매칭 수를 구하면 정답이 나온다. 

 

// Reference: green55 teamnote
// https://github.com/green5555/Teamnote/blob/master/TeamNote/BiMatch.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2001;
struct BiMatching {
    vector<int> adj[MAX+5];
    int iter, A[MAX+5], B[MAX+5], was[MAX+5];

    bool dfs(int u) {
        was[u] = iter;
        for (int v : adj[u]) {
            if (B[v] == -1) {
                A[u] = v;
                B[v] = u;
                return true;
            }
        }
        for (int v : adj[u]) {
            if (was[B[v]] != iter && dfs(B[v])) {
                A[u] = v;
                B[v] = u;
                return true;
            }
        }
        return false;
    }

    int biMatch(int n=MAX) {
        fill(A, A+n, -1);
        fill(B, B+n, -1);
        fill(was, was+n, 0);
        iter = 0;
        int res = 0;
        while (true) {
            iter++;
            int add = 0;
            for (int i = 0; i < n; i++) {
                if (A[i] == -1 && dfs(i)) {
                    add++;
                }
            }
            if (add == 0) {
                break;
            }
            res += add;
        }
        return res;
    }
};

void solve() {
    BiMatching bm;

    int n, m;
    cin >> n >> m;

    for (int i = 1; i < n + 1; i++) {
        int k;
        cin >> k;
        while (k--) {
            int j;
            cin >> j;
            bm.adj[i].push_back(j + 1000);
        }
    }

    cout << bm.biMatch() << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)