6241번: Dining

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

최대 유량을 구하는 문제로 바꿔 풀 수 있다.

소가 i번이면 용량 1의 i - i' 간선을 추가한다.
i번 소가 food fi를 좋아하면 용량 1의 source -> fi, fi -> i 간선을 추가한다.
i번 소가 drink di를 좋아하면 용량 1의 i' -> di, di -> sink 간선을 추가한다.
답은 이 그래프에서 최대 유량이 된다.

시간복잡도는 $O(V^3)$ // V = N + F + D

#include<cstdio>
#include<cstring>
int n, f, d, c[402][402], res, vis[402];
int dfs(int h) {
    vis[h] = 1;
    for (int i = 0; i < 402; i++) if (c[h][i] && (i == 401 || !vis[i] && dfs(i))) {
        c[h][i]--;
        c[i][h]++;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d%d", &n, &f, &d);
    for (int i = 1, fi, di, x; i <= n; i++) {
        scanf("%d%d", &fi, &di);
        for (int j = 0; j < fi; j++) scanf("%d", &x), c[0][200 + x] = c[200 + x][i] = 1;
        for (int j = 0; j < di; j++) scanf("%d", &x), c[100 + i][300 + x] = c[300 + x][401] = 1;
        c[i][100 + i] = 1;
    }
    for (int ret; ret = dfs(0);) memset(vis, 0, sizeof(vis)), res += ret;
    printf("%d", res);
    return 0;
}