티스토리 뷰

알고리즘 관련/BOJ

BOJ)9577 토렌트

JASON 자손9319 2017. 2. 22. 22:54

문제: icpc.me/9577


시간마다 시드를 하나씩 받을 수 있고 각 시간에 시드를 받을 수 있는 사람과 각 사람이 받을 수 있는 시드의 종류가 주어졌을 때 시드를 전부 다운 받는 최소 시간을 출력하는 문제이다.


우리는 시간에 대한 정점과 시드에 대한 정점으로 나누어 이분 그래프를 형성해 준 다음 이분 매칭을 시도하는데 시간 정점중 t번째 정점까지 매칭 했을 때 최대매칭이 시드의 수와 일치할 경우 t초가 최단시간이 된다.


 

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t;
struct BipartiteMatching {
    int n, m, b[101], visited[101];
    vector<vector<int>> vt;
    bool 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 f() {
        int maxflow = 0;
        for (int i = 0; i < 100; i++) {
            memset(visited, 0sizeof(visited));
            if (dfs(i))maxflow++;
            if (maxflow == n)return i + 1;
        }
        return -1;
    }
    void func() {
        memset(b, -1sizeof(b));
        scanf("%d%d"&n, &m);
        vt.resize(101);
        int lt, ht, k, x;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d"&lt, &ht);
            scanf("%d"&k);
            while (k--) {
                scanf("%d"&x);
                for (int j = lt; j < ht; j++) {
                    vt[j].push_back(x);
                }
            }
        }
        printf("%d\n", f());
    }
};
int main() {
    scanf("%d"&t);
    while (t--) {
        BipartiteMatching bm;
        bm.func();
    }
    return 0;
}
cs


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

BOJ)2916 자와 각도기  (0) 2017.03.01
BOJ)3049 다각형의 대각선  (0) 2017.03.01
BOJ)9577 토렌트  (0) 2017.02.22
BOJ)5430 AC  (0) 2017.02.21
BOJ)1966 프린터 큐  (0) 2017.02.21
BOJ)6064 카잉 달력  (0) 2017.02.21
댓글
댓글쓰기 폼