[백준 11377] 열혈강호 3

문제

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

 

알고리즘

이분매칭

 

풀이

열혈강호 시리즈 세 번째 문제입니다. 열혈강호 2와 같이 한 사람당 최대 두 개의 일을 한다는 점은 같지만 추가 매칭이 최대 K번 가능한 점이 다릅니다. 비슷한 문제이므로, 비슷하게 풀 수 있습니다. $bipartite matching()$에서 $N$까지 루프를 한번 돌려서 한 사람당 한가지 일을 하도록 매칭을 한 후, 다시 루프를 돌며 추가매칭이 K번 이하 이루어졌다면 계속해서 매칭을 해주면 됩니다. 역시 시간 복잡도는 $O(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];
bool 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 true;
        }
    }
    return false;
}

int bipartite_matching() {
    int ret = 0;
    REP(i, N) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ++ret;
    }
    REP(i, N) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i) && K) --K, ++ret;
    }
    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;
}