백준 11375번 열혈강호 - C++(cpp) 풀이

---

 

1. 직원과 일 사이의 관계를 이분 그래프로 만든다.
2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다.

 

1. 직원과 일 사이의 관계를 이분 그래프로 만든다.

 각 직원과 일을 정점으로 생각하고, 각 직원과 그 직원이 할 수 있는 일들을 간선으로 이어 이분 그래프를 만든다.

 

2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다.

 최대로 할 수 있는 일의 개수는, 완성된 이분 그래프에서 직원 그룹과 일 그룹 사이의 최대 매칭의 수와 같다. 따라서 이분 매칭 알고리즘을 사용해 최대 매칭 수를 구해주면 된다.

 

반응형

---

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

const int MAX = 1001;

int N, M;
vector<int> works[MAX];
int owner[MAX];
bool visit[MAX];

bool DFS(int curr) {
    if (visit[curr]) return false;
    visit[curr] = true;
    
    for (auto work: works[curr]) {
        if (!owner[work] || DFS(owner[work])) {
            owner[work] = curr;
            return true;
        }
    }
    
    return false;
}

int bipartite_match() {
    int ret = 0;
    
    for (int i=1; i<=N; i++) {
        memset(visit, 0, sizeof(visit));
        if (DFS(i)) ret++;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    int k, w;
    for (int i=1; i<=N; i++) {
        cin >> k;
        
        for (int j=0; j<k; j++) {
            cin >> w;
            works[i].push_back(w);
        }
    }
    
    cout << bipartite_match();

    return 0;
}