[C++] 백준 11378번 열혈강호 4

이분매칭으로 문제를 해결했습니다.

https://j3sung.tistory.com/409

[C++] 백준 11375번 열혈강호

이 문제와 같이 일을 한개할 때의 경우를 계산합니다.

그리고 추가적으로 일을 할 수 있는 경우를 찾습니다.
찾는 경우 카운트를 증가해주고 벌점의 수만큼 이를 반복해줍니다.

중간에 추가적으로 할 수 있는 경우가 없으면
반복문을 종료하고 count를 출력합니다.

 

#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[]) 
{
	bool flag = true;
	int n, m, k;
	int c;
	int num;
	int count = 0;

	scanf("%d", &n);
	scanf("%d", &m);
	scanf("%d", &k);

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &c);
		for (int j = 0; j < c; ++j) {
			scanf("%d", &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;
		}
	}

	while (k > 0 && flag) {
		for (int i = 1; i <= n; ++i) {
			fill(visit, visit + 1010, false);
			if (DFS(i)) {
				flag = true;
				++count;
				--k;
				break;
			}
			else {
				flag = false;
			}
		}
	}

	printf("%d\n", count);

	return 0;
}