BOJ)14433 한조 대기 중

문제: icpc.me/14433

A팀과 B팀에 각각 N,M의 유저가 원하는 트롤픽의 목록이 주어질 때 트롤픽을 최대로 선택하여 어떤 팀이 이기게 될지 알아보는 문제이다.

A팀의 그래프와 B팀의 그래프를 각각 이분매칭에서의 최대매칭을 구해준 뒤 비교해서 답을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, m, check[5000], backmatch[5000], k1, k2, x, y, r, a;
vector<vector<int>> vt;
vector<vector<int>> wt;
bool dfs(int here, const vector<vector<int>>& v) {
    if (here == -1) return true;
    for (int next : v[here]) {
        if (check[next])continue;
        check[next] = true;
        if (dfs(backmatch[next], v)) {
            backmatch[next] = here;
            return true;
        }
    }
    return false;
}
int bmatch(const vector<vector<int>> & v) {
    memset(backmatch, -1, sizeof(backmatch));
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        memset(check, 0, sizeof(check));
        if (dfs(i, v))
            ret++;
    }
    return ret;
}
int main(){
    scanf("%d%d%d%d", &n, &m, &k1, &k2);
    vt.resize(5000);
    wt.resize(5000);
    for (int i = 0; i < k1; i++) {
        scanf("%d%d", &x, &y);
        vt[x].push_back(y);
    }
    for (int i = 0; i < k2; i++) {
        scanf("%d%d", &x, &y);
        wt[x].push_back(y);
    }
    r = bmatch(vt);
    a = bmatch(wt);
    printf("%s\n", r < a ? "네 다음 힐딱이" : "그만 알아보자");
    return 0;
}