이분 매칭으로 문제를 해결하였습니다.
N명의 직원이 있고 해야할 일이 M개가 있을 때
직원들이 할 수 있는 일들이 정해져있고 하나의 일만 할 수 있습니다.
이 때 일을 잘 분배해서 가장 많이 할 수 있는 일의 수를 찾는 문제입니다.
A집단과 B집단을 매칭해야하는 경우이므로 이분매칭을 사용할 수 있습니다.
1. 매칭이 되어 있지 않으면 매칭
2. 매칭이 되어 있으면 매칭되어 있는 곳에서 다른 곳에 매칭이 되는지 확인
3. 불가능하면 다른 곳 매칭이 가능한지 확인
4. 모든 곳이 매칭 불가능하면 그 위치는 매칭이 안되는 곳으로 확인
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[1010];
int work[1010];
bool finish[1010];
bool DFS(int x)
{
for (int i = 0; i < v[x].size(); ++i) {
int t = v[x][i];
if (finish[t]) {
continue;
}
finish[t] = true;
if (work[t] == 0 || DFS(work[t])) {
work[t] = x;
return true;
}
}
return false;
}
int main(int argc, char *argv[])
{
int n, m;
int c;
int num;
int count = 0;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> c;
for (int j = 0; j < c; ++j) {
cin >> num;
v[i].push_back(num);
}
}
fill(work, work + 1010, 0);
for (int i = 1; i <= n; ++i) {
fill(finish, finish + 1010, false);
if (DFS(i)) {
++count;
}
}
cout << count << endl;
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 11377번 열혈강호 3 (0) | 2019.10.13 |
---|---|
[C++] 백준 11376번 열혈강호 2 (0) | 2019.10.13 |
[C++] 백준 16282번 Black Chain (0) | 2019.10.02 |
[C++] 백준 16283번 Farm (0) | 2019.10.02 |
[C++] 백준 1789번 수들의 합 (0) | 2019.10.02 |