백준 11377번 열혈강호 3

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

11377번: 열혈강호 3

열혈강호 2(https://jaimemin.tistory.com/1512)와 유사한 문제였습니다.

이 문제에서는 N명 중에서 K명만 일을 최대 두 개 할 수 있고 나머지 직원은 한 개의 일을 할 수 있으므로 열혈강호 2처럼 직원의 수를 두배로 늘리되 우선 짝수번째 인덱스에 있는 직원을 먼저 업무에 배치를 하고 이후에 홀수번째 인덱스에 있는 직원 중 K명을 다른 업무에 배치를 해줍니다.

 

	#include <iostream>
	#include <vector>
	#include <cstring>
	using namespace std;
	const int MAX = 1e3 * 2 + 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 * 2].push_back(work - 1);
	works[i * 2 + 1].push_back(work - 1);
	}
	}
	memset(worker2work, -1, sizeof(worker2work));
	memset(work2worker, -1, sizeof(work2worker));
	int result = 0;
	for (int worker = 0; worker < N * 2; worker += 2)
	{
	if (worker2work[worker] == -1)
	{
	memset(visited, false, sizeof(visited));
	if (func(worker))
	{
	result++;
	}
	}
	}
	int specialWorkers = 0;
	for (int worker = 1; worker < N * 2; worker += 2)
	{
	if (worker2work[worker] == -1)
	{
	memset(visited, false, sizeof(visited));
	if (func(worker))
	{
	result++;
	specialWorkers++;
	if (specialWorkers == K)
	{
	break;
	}
	}
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

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