끄적끄적 코딩
article thumbnail

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

https://j3sung.tistory.com/409

 

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

이분 매칭으로 문제를 해결하였습니다. N명의 직원이 있고 해야할 일이 M개가 있을 때 직원들이 할 수 있는 일들이 정해져있고 하나의 일만 할 수 있습니다. 이 때 일을 잘 분배해서 가장 많이 할 수 있는 일의..

j3sung.tistory.com

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

검색 태그