이분 매칭을 통해서 문제를 해결했습니다.
https://j3sung.tistory.com/409
열혈강호를 푼 방식과 동일하며, 다른점은 일을 두 가지 할 수 있다는 점입니다.
각 정점에 대해서 이분매칭을 두번 해주었습니다.
#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) {
for (int j = 1; j <= 2; ++j) {
fill(finish, finish + 1010, false);
if (DFS(i)) {
++count;
}
}
}
cout << count << endl;
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 11378번 열혈강호 4 (0) | 2019.10.13 |
---|---|
[C++] 백준 11377번 열혈강호 3 (0) | 2019.10.13 |
[C++] 백준 11375번 열혈강호 (0) | 2019.10.13 |
[C++] 백준 16282번 Black Chain (0) | 2019.10.02 |
[C++] 백준 16283번 Farm (0) | 2019.10.02 |