boj, 백준) 11377. 열혈강호 3 ( C / C++ )

1. 문제 링크

https://www.acmicpc.net/problem/11377

11377번: 열혈강호 3

2. 문제 개요

직원 N명, M개의 일 N명 중에서 K명은 일을 최대 2개 할 수 있을 때, 일을 최대 몇 개를 할 수 있는지 구하는 프로그램 작성하기.

3. 문제 힌트

 K명은 일을 한번 더 할 수 있다는 말은

일 1개씩 하는 이분매칭 + 최대 K = 답이 된다.

즉, 이분탐색을 한번 더 하고 누가 됐든 간에 어느 사람들이 K번(K개와 매칭)하면 종료하기.

 

4. 문제 풀이

우선

열혈강호 1번 문제 처럼 이분 매칭을 1번 한다.

https://kibbomi.tistory.com/41

boj, 백준) 11375. 열혈강호 (C / C++)

이분 매칭을 1번 했다는 말은 각자 1가지 일을 한다고 가정했을 때 가장 많이 일을 할 수 있는 상태로 선택되어 있다고 볼 수 있다.

 

여기서, 이분매칭을 1번 더 시도하는데 count변수를 두어 누군가가 일을 1개 더 맡게 된다면 count변수를 증가시킨다. 예를 들면 '꼭 1, 3번 사람이 일을 2번 해야 한다' 이런 것도 아니기 때문에, 누가 됐든 간에 최대 K명이 될 때까지 count값을 증가시키며 이분 탐색을 한 번 더 한다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, k;
vector<int> v[1001];	//use 1~n index
bool visited[1001] = { false, };
int matched[1001]; 

bool dfs(int cur)
{
	if (visited[cur])
		return false;

	visited[cur] = true;

	int len = v[cur].size();

	for (int i = 0; i < len; ++i)
	{
		int next = v[cur][i];

		if (matched[next] == 0 || dfs(matched[next]))
		{
			matched[next] = cur;
			return true;
		}
	}
	return false;
}

int main()
{
	int ans = 0;

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

	for (int i = 1; i <= n; ++i)
	{
		int count;
		scanf("%d", &count);

		for (int j = 0; j < count; ++j)
		{
			int to;
			scanf("%d", &to);

			v[i].push_back(to);
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		fill(visited, visited + 1001, false);
		if (dfs(i))
			ans++;
	}
	int count = 0;

	for (int i = 1; i <= n; ++i)
	{
		fill(visited, visited + 1001, false);
		if (dfs(i)) {
			ans++;
			count++;
		}
		if (count == k)	break;
	}
	printf("%d", ans);
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~