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

---

 

1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다.
2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다.

 

1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다.

 직원 그룹과 일 그룹 사이의 최대 매칭의 수를 구하는 문제이다.

 

2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다.

 각 직원당 최대 2개의 일을 할 수 있으므로, 직원을 기준으로 하는 이분 매칭을 2번 진행하여 이루어진 총 매칭의 수를 구해주면 된다.

 

반응형

---

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

using namespace std;

const int MAX = 1001;

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

bool DFS(int emp) {
    if (visit[emp]) return false;
    visit[emp] = true;
    
    for (auto work: works[emp]) {
        if (!owner[work] || DFS(owner[work])) {
            owner[work] = emp;
            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 wn, work;
    for (int emp=1; emp<=N; emp++) {
        cin >> wn;
        
        for (int i=0; i<wn; i++) {
            cin >> work;
            works[emp].push_back(work);
        }
    }
    
    cout << bipartite_match() + bipartite_match();

    return 0;
}