본문 바로가기

알고리즘 관련/BOJ

BOJ)3736 System Engineer

문제: icpc.me/3736


작업 세트와 서버로 이루어진 이분 그래프에서 최대 매칭을 구하는 문제이다.


정점의 개수가 10000개 이므로 일반 이분 매칭 소스로는 TLE가 나므로 hopcroft-karp 알고리즘을 이용하여 최대매칭을 구해줘야 한다.



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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
struct hopcroft_karp {
    int n;
    vector<int> a, b, dist, match, work;
    vector<vector<int>> vt;
    hopcroft_karp(int n) :n(n) {
        a.assign(n + 1-1);
        b.assign(n + 1-1);
        dist.assign(n + 10);
        match.assign(n + 10);
        vt.resize(n + 1);
    }
    void addEdge(int x, int y) {
        vt[x].push_back(y);
    }
    void bfs() {
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
            if (!match[i]) {
                dist[i] = 0;
                qu.push(i);
            }
            else
                dist[i] = INF;
        }
        while (qu.size()) {
            int here = qu.front();
            qu.pop();
            for (auto there : vt[here]) {
                if (b[there] != -&& dist[b[there]] == INF) {
                    dist[b[there]] = dist[here] + 1;
                    qu.push(b[there]);
                }
            }
        }
    }
    bool dfs(int here) {
        for (int &= work[here]; i < vt[here].size(); i++) {
            int there = vt[here][i];
            if (b[there] == -|| dist[b[there]] == dist[here] + && dfs(b[there])) {
                match[here] = true;
                a[here] = there;
                b[there] = here;
                return true;
            }
        }
        return false;
    }
    int solve() {
        int ret = 0;
        while (1) {
            work.assign(n + 10);
            bfs();
            int flow = 0;
            for (int i = 1; i <= n; i++)
                if (!match[i] && dfs(i))flow++;
            if (!flow)break;
            ret += flow;
        }
        return ret;
    }
};
int n, m, x, y;
int main() {
    while (scanf("%d"&n) != EOF) {
        hopcroft_karp hk(n);
        for (int i = 0; i < n; i++) {
            scanf("%d: (%d)"&x, &m);
            for (int j = 0; j < m; j++) {
                scanf("%d"&y);
                hk.addEdge(x + 1, y - n + 1);
            }
        }
        printf("%d\n", hk.solve());
    }
    return 0;
}
cs


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

BOJ)1326 폴짝폴짝  (0) 2017.03.26
BOJ)13166 범죄 파티  (0) 2017.03.25
BOJ)2660 회장뽑기  (0) 2017.03.23
BOJ)1755 숫자놀이  (0) 2017.03.23
BOJ)1747 소수&팰린드롬  (0) 2017.03.23