boj, 백준) 2367. 파티 (C/C++)

1. 문제 링크

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

2367번: 파티

2. 문제 개요

N(3 ≤ N ≤ 200) 명의 사람이 파티를 하려고 한다. 각각의 사람은 몇 종류의 음식을 요리할 줄 안다. 각 음식의 종류는 1부터 D(5 ≤ D ≤ 100) 까지의 정수로 표현된다.

 

각각의 사람이 가져올 수 있는 음식의 양에 제한이 있다. 각각의 사람은 최대 K(1 ≤ K ≤ 5) 개의 접시 밖에 가져올 수 없다. 이때, 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자. 또, 각 음식의 종류 마다도 가져올 수 있는 양에 제한이 있다.

 

이와 같은 제한들이 주어졌을 때, 파티에 준비될 수 있는 접시의 개수의 최댓값을 알아내는 프로그램을 작성.

3. 문제 힌트

문제가 정말 깨끗하지 못한 것 같다고 해야할까.. 알아듣기 정말 힘들었다. (제가 멍청한 것 일 수도..)

 

문제는 정말 복잡하지만 전형적인 네트워크 플로우 문제다.

어떻게 모델링하면 위 문제를 잘 묘사할 수 있을까?

 

4. 문제 풀이

네트워크 플로우 문제라는 점, 네트워크 플로우 알고리즘을 알고 있다면 쉽게 해결할 수 있기 때문에 특별히 힌트?랄것은 없다.

 

모델링이 문제인데..

문제에 나와있는 조건들이 그래프에서 간선의 용량 등을 의미한다.

 

1) 각각의 사람이 가져올 수 있는 음식의 양 : Source ⇔ 사람 사이 간선의 용량

2) 이때 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자 : 사람 ⇔ 음식 간선의 용량

3) 음식의 종류마다도 가져올 수 있는 양에 제한이 있다. : 음식 ⇔ Sink 간선의 용량

 

이 부분을 잘 캐치해서 그래프를 그려보면

예제 입력 기준으로

4 3 5

2 2 2 2 3

4 1 2 3 4

4 2 3 4 5

3 1 2 4

3 1 2 3

그림판..

src - 사람 - 음식 - sink, 이렇게 모델링할 수 있다.

 

밑의 코드는 Dinic알고리즘을 사용해서 문제를 푼 코드이다.

 

5. 코드

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

constexpr int bias = 200, src = 0, sink = 301, SIZE = 302;
//N : [1,200], D : [201, 300]

int flow[SIZE][SIZE], capacity[SIZE][SIZE];
vector<int> adj[SIZE];
int n, k, d, ans;
int level[SIZE];

bool leveling()
{
	queue<pair<int,int>> q;	
	fill(level, level + SIZE, -1);

	q.push({ src,0 });
	level[src] = 0;

	while (!q.empty())
	{
		int cur = q.front().first;
		int lv = q.front().second;
		q.pop();

		for (int next : adj[cur])
		{
			if (level[next] == -1 && capacity[cur][next] - flow[cur][next] > 0)
			{
				level[next] = level[cur] + 1;
				q.push({ next,level[next] });
			}
		}
	}

	//sink까지 도달 했다면 true반환 하도록 
	return level[sink] != -1;
}

int dfs(int cur, int minflow)
{
	//base condition
	if (cur == sink)
		return minflow;

	for (int next : adj[cur])
	{
		if (level[next] == level[cur] + 1 && capacity[cur][next] - flow[cur][next] > 0)
		{
			int ret = dfs(next, min(minflow, capacity[cur][next] - flow[cur][next]));

			if (ret > 0)
			{
				flow[cur][next] += ret;
				flow[next][cur] -= ret;
				return  ret;
			}

		}
			
	}
	//fail
	return 0;
}

int main()
{
	scanf("%d %d %d", &n, &k, &d);

	for (int i = 1; i <= d; ++i) {
		scanf("%d", &capacity[bias + i][sink]);   //food -> sink

		adj[bias + i].push_back(sink);
		adj[sink].push_back(bias + i);
	}

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

		capacity[src][i] = k;   //src - chef
		adj[src].push_back(i);
		adj[i].push_back(src);

		while (cnt--)
		{
			int food;
			scanf("%d", &food);

			capacity[i][bias + food] = 1;   //chef - food
			adj[i].push_back(bias + food);
			adj[bias + food].push_back(i);
		}
	}


	while (leveling())
	{
		while(1)
		{
			int ret = dfs(src, 987654321);
			if (ret == 0)
				break;
			ans += ret;
		}
	}

	printf("%d", ans);

		return 0;
}

 

 

6. 결과