이분매칭으로 문제를 해결했습니다.
https://j3sung.tistory.com/409
11375 열혈강호와 유사한 문제입니다.
다른점으로는 2개의 일을 할 수 있는 사람이 k명 있는 점입니다.
1개의 일을 할 수 있는 경우에 대해서 11375번 문제와 동일하게 풀고
다시 첫번째 사람부터 마지막 사람까지 일을 할 수 있는 경우를 찾습니다.
이는 최소 0번부터 최대 K번까지 가능합니다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[1010];
int work[1010];
bool visit[1010];
bool DFS(int x)
{
for (int i = 0; i < v[x].size(); ++i) {
int t = v[x][i];
if (visit[t]) {
continue;
}
visit[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, k;
int c;
int num;
int count = 0;
cin >> n >> m >> k;
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(visit, visit + 1010, false);
if (DFS(i)) {
++count;
}
}
for (int i = 1; i <= n; ++i) {
fill(visit, visit + 1010, false);
if (DFS(i)) {
++count;
--k;
if (k == 0) {
break;
}
}
}
cout << count << endl;
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 17520번 Balanced String (0) | 2019.10.14 |
---|---|
[C++] 백준 11378번 열혈강호 4 (0) | 2019.10.13 |
[C++] 백준 11376번 열혈강호 2 (0) | 2019.10.13 |
[C++] 백준 11375번 열혈강호 (0) | 2019.10.13 |
[C++] 백준 16282번 Black Chain (0) | 2019.10.02 |