티스토리 뷰

알고리즘 관련/BOJ

BOJ)14433 한조 대기 중

JASON 자손9319 2017. 2. 6. 02:26

문제: icpc.me/14433


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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 == -1return 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, -1sizeof(backmatch));
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        memset(check, 0sizeof(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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)9934 완전 이진 트리  (0) 2017.02.06
BOJ)1562 계단 수  (0) 2017.02.06
BOJ)14433 한조 대기 중  (0) 2017.02.06
BOJ)14431 소수마을  (0) 2017.02.06
BOJ) 10282 Failing Components  (0) 2017.02.04
BOJ)9202 Boggle  (0) 2017.02.04
댓글
댓글쓰기 폼