끄적끄적 코딩
article thumbnail

이분 매칭을 통해서 문제를 해결했습니다.

https://j3sung.tistory.com/409

 

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

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

j3sung.tistory.com

열혈강호를 푼 방식과 동일하며, 다른점은 일을 두 가지 할 수 있다는 점입니다.
각 정점에 대해서 이분매칭을 두번 해주었습니다.

 

#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

검색 태그