티스토리 뷰

알고리즘 관련/BOJ

BOJ)10276 Jewelry Exhibition

JASON 자손9319 2017. 8. 1. 14:50

문제: icpc.me/10276


각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다.


x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 


결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다.


이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int t, n, m, k, visited[202], b[202];
vector<vector<int>> vt;
int dfs(int here) {
    if (visited[here])return false;
    visited[here] = true;
    for (auto next : vt[here]) {
        if (!b[next] || dfs(b[next])) {
            b[next] = here;
            return true;
        }
    }
    return false;
}
int bipartitematching() {
    int ret = 0;
    memset(b, 0sizeof(b));
    for (int i = 1; i <= n; i++) {
        memset(visited, 0sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d%d"&n, &m, &k);
        vt.clear();
        vt.resize(n + 1);
        for (int i = 0; i < k; i++) {
            double x, y;
            scanf("%lf%lf"&x, &y);
            int xx = (int)x, yy = (int)y;
            vt[xx + 1].push_back(yy + 1);
        }
        printf("%d\n", bipartitematching());
    }
    return 0;
}
cs


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

BOJ)5721 사탕 줍기 대회  (0) 2017.08.01
BOJ)11560 다항식 게임  (0) 2017.08.01
BOJ)10276 Jewelry Exhibition  (0) 2017.08.01
BOJ)1999 최대최소  (0) 2017.07.31
BOJ)13511 트리와 쿼리2  (0) 2017.07.31
BOJ)14657 준오는 최종인재야!!  (0) 2017.07.29
댓글
댓글쓰기 폼