11378번: 열혈강호 4

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

이분 매칭 문제로 만들어 풀 수 있다.
먼저, 직원과 일을 일대일 매칭시킨다. 그리고 나서 벌점을 배분하는데, 매칭이 되지 않은 일 중 해당 일을 할 수 있는 직원(처음에 매칭되었던 직원이라도 상관없다.)이 있다면 그러한 직원 아무에게나 1점의 벌점을 매기고 해당 일을 하도록 할 수 있다.
고로 답은 min( (일대일 매칭 수) + k, (직원 누군가 할 수 있는 일의 개수) )

시간복잡도는 $O(V^3)$ // V = n+m

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int vis[1001], rev[1001], n, m, k, ck[1001], cnt, c;
vector<int> adj[1001];
int dfs(int h) {
    vis[h] = c;
    for (int it : adj[h]) if (!rev[it] || vis[rev[it]] ^ c && dfs(rev[it])) {
        rev[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x, y; i <= n; i++) for (scanf("%d", &x); x--;) {
        scanf("%d", &y);
        adj[i].push_back(y);
        cnt += !ck[y]++;
    }
    for (c = 1; c <= n; c++) k += dfs(c);
    printf("%d", min(k, cnt));
    return 0;
}