BOJ)9577 토렌트

문제: icpc.me/9577

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

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

 

#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] == -1 || dfs(b[next])) {
                b[next] = here;
                return true;
            }
        }
        return false;
    }
    int f() {
        int maxflow = 0;
        for (int i = 0; i < 100; i++) {
            memset(visited, 0, sizeof(visited));
            if (dfs(i))maxflow++;
            if (maxflow == n)return i + 1;
        }
        return -1;
    }
    void func() {
        memset(b, -1, sizeof(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;
}