[백준 11378] 열혈강호 4

문제

https://www.acmicpc.net/problem/11378

 

알고리즘

이분매칭

 

풀이

열혈강호 3과 달라진 점은 한 사람당 최대 두 가지의 일을 할 수 있었던 3번 문제에 반해, 열혈강호 4는 벌점에 따라 한 사람당 최대할 수 있는 일의 수가 달라진다는 점입니다. 비슷하므로 비슷하게 풀어봅시다.

마찬가지로 $N$까지 루프를 한번 돌려 한 사람당 한 가지 일을 매칭해주도록 합시다. 열혈강호 3에선 추가적으로 루프를 한 번만 더 돌려서 한 사람당 최대 두 가지 일을 할 수 있다 라는 점을 구현하였는데, 이 문제에선 추가 매칭이 이루어지지 않을 때까지 루프를 돌립니다. 즉 $K$를 다 사용하거나, 아직 $K$가 남아있지만 더 이상 사람이 일을 할 수 없을 때를 뜻합니다. 시간 복잡도는 $O(K*VE)$입니다.

 

코드

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M, K,cnt,x;

vector<vector<int>> adj;

bool visited[1001];
int match[1001];

int dfs(int here) {
    visited[here] = true;
    for (auto there : adj[here]) {
        int u = match[there];
        if (!u || !visited[u] && dfs(u)) {
            match[there] = here;
            return 1;
        }
    }
    return 0;
}

int bipartite_matching() {
    int ret = 0;
    REP(i, N) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ++ret;
    }
    while (1) {
        bool update = false;
        REP(i, N) {
            memset(visited, 0, sizeof(visited));
            if (dfs(i) && K) --K, ++ret,update=true;
        }
        if (!update) break;
    }
    return ret;
}


int main() {
    FAST;
    cin >> N >> M >> K;
    adj.resize(N + 1);
    REP(i,N) {
        cin >> cnt;
        while (cnt--) {
            cin >> x;
            adj[i].emplace_back(x);
        }
    }
    cout << bipartite_matching();

    return 0;
}