티스토리 뷰

알고리즘 관련/BOJ

BOJ)1733 등번호

JASON 자손9319 2017. 1. 3. 15:11

문제: icpc.me/1733


참가자와 등번호들로 이루어진 이분 그래프를 이분매칭하는 문제이다.


이분 매칭의 역추적은 매칭을 시킬 때 배열등에 저장하여 쉽게 할 수 있다.


다만 N이 100만이므로 매칭때마다 memset을 사용할 경우 TL을 볼 수도 있다.


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
48
49
50
51
52
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> vt;
int check[1000100];
int backmatch[1000100];
int r[1000100];
int n, x, y, s;
bool dfs(int here) {
    if (here == -1return true;
    for (int next : vt[here]) {
        if (check[next] == s)continue;
        check[next] = s;
        if (dfs(backmatch[next])) {
            backmatch[next] = here;
            r[here] = next;
            return true;
        }
    }
    return false;
}
int bmatch() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        s = i;
        if (dfs(i))
            ret++;
    }
    return ret;
}
 
int main()
{
    scanf("%d"&n);
    vt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d"&x, &y);
        vt[i].push_back(x);
        vt[i].push_back(y);
    }
    memset(backmatch, -1sizeof(backmatch));
    int res = bmatch();
    if (res != n)
        printf("-1\n");
    else {
        for (int i = 1; i <= n; i++)
            printf("%d\n", r[i]);
    }
    return 0;
}
cs



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

BOJ)12844 XOR  (0) 2017.01.03
BOJ)10815 숫자 카드  (0) 2017.01.03
BOJ)1733 등번호  (2) 2017.01.03
BOJ)14168 Cow Checklist  (0) 2017.01.03
BOJ)11895 속이기  (0) 2017.01.03
BOJ)2401 최대 문자열 붙여넣기  (1) 2016.12.30
댓글
댓글쓰기 폼