백준 11378번 열혈강호 4

문제 링크입니다: https://www.acmicpc.net/problem/11378

11378번: 열혈강호 4

기존의 열혈강호 문제들과 마찬가지로 이분매칭 알고리즘을 통해 풀 수 있는 문제였습니다.

열혈강호: https://jaimemin.tistory.com/1352

열혈강호 2: https://jaimemin.tistory.com/1512

열혈강호 3: https://jaimemin.tistory.com/1513

 

알고리즘은 아래와 같습니다.

1. 직원을 한 쪽, 업무를 반대 쪽으로 배치하고 우선 직원에 대해 가능한 매칭을 진행합니다.

2. 이후에는 최대한 많이 직원과 업무를 매칭을 해줍니다. (최대 K개 업무이므로 매칭이 불가하다면 K개 미만의 업무를 추가적으로 할 수도 있기 때문에 for문 종료 조건에 worker < N && points < K) 

 

	#include <iostream>
	#include <vector>
	#include <cstring>
	using namespace std;
	const int MAX = 1e3 + 1;
	int N, M, K;
	vector<int> works[MAX];
	int worker2work[MAX], work2worker[MAX];
	bool visited[MAX];
	bool func(int worker)
	{
	for (int workNum : works[worker])
	{
	if (visited[workNum])
	{
	continue;
	}
	visited[workNum] = true;
	if (work2worker[workNum] == -1 || func(work2worker[workNum]))
	{
	worker2work[worker] = workNum;
	work2worker[workNum] = worker;
	return true;
	}
	}
	return false;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
	int cnt;
	cin >> cnt;
	for (int j = 0; j < cnt; j++)
	{
	int work;
	cin >> work;
	works[i].push_back(work - 1);
	}
	}
	memset(worker2work, -1, sizeof(worker2work));
	memset(work2worker, -1, sizeof(work2worker));
	int result = 0;
	for (int worker = 0; worker < N; worker++)
	{
	if (worker2work[worker] == -1)
	{
	memset(visited, false, sizeof(visited));
	if (func(worker))
	{
	result++;
	}
	}
	}
	int points = 0;
	while (1)
	{
	bool flag = false;
	for (int worker = 0; worker < N && points < K; worker++)
	{
	memset(visited, false, sizeof(visited));
	if (func(worker))
	{
	result++;
	flag = true;
	points++;
	break;
	}
	}
	if (flag == false)
	{
	break;
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~