[BOJ 2367] 파티

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

2367번: 파티

 

- 문제 요약

 

N(3 ≤ N ≤ 200)명의 사람이 파티를 하려고 한다.

 

각각의 사람은 몇 종류의 음식을 요리할 줄 안다. 각각의 음식의 종류는 1부터 D(5 ≤ D ≤ 100)까지의 정수로 표현된다.

파티를 위해서 각각의 사람이 요리를 해서 가져오기로 했는데, 가급적이면 많은 접시의 음식을 파티에 준비하려 한다.

 

또한 각각의 사람이 가져올 수 있는 음식의 양에 제한이 있다.

각각의 사람은 최대 K(1 ≤ K ≤ 5)개의 접시밖에 가져올 수 없다고 하자.

이때 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자.

 

또한 각 음식의 종류마다도 가져올 수 있는 양에 제한이 있다.

사전에 파티 참석자들에게 음식 선호도 조사를 하여 낭비되는 음식이 없도록 양을 정했다.

 

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

 

 

- 알고리즘 정리

 

https://www.crocus.co.kr/1088

디닉 알고리즘(Dinic's Algorithm)

(위 블로그를 참고하여 작성한 풀이입니다)

 

네트워크 플로우로 풀면 되는 문제입니다.

테스트 케이스 1번을 기준으로 네트워크 플로우 모델을 아래와 같이 만들었습니다.

 

Network Flow Modeling (Tast Case #1)

 Source에서 N명의 사람(TC#1에서는 4명)에 K(TC#1에서는 3)만큼의 Capacity를 할당해 줍니다.

그리고 문제에서 나온 "이때 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자."를 이용해서 간선을 만들어줍니다.

사람에서 음식의 종류로 간선을 이어주고(Capacity = 1), 각 음식의 종류에서 Sink로 가져올 수 있는 개수를 Capacity로 해서 간선을 하나 더 추가해 줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 302
#define INF 987654321
int n,k,d,flow[MAX][MAX],cap[MAX][MAX],result,arr[MAX],src=0,sink=MAX-1,bias=200;
vector<int>adj[MAX];

bool f(){
	queue<pair<int,int> >q;
	fill(arr,arr+MAX,-1);
	q.push({src,0});
	arr[src]=0;
	while(!q.empty()){
		int cur=q.front().first;
		int lv=q.front().second;
		q.pop();
		for(int i:adj[cur]){
			if(arr[i]==-1&&cap[cur][i]-flow[cur][i]>0){
				arr[i]=arr[cur]+1;
				q.push({i,arr[i]});
			}
		}
	}
	return arr[sink]!=-1;
}

int dfs(int cur,int mn){
	if(cur==sink){
		return mn;
	}
	for(int i:adj[cur]){
		if(arr[i]==arr[cur]+1&&cap[cur][i]-flow[cur][i]>0){
			int ret=dfs(i,min(mn,cap[cur][i]-flow[cur][i]));
			if(ret>0){
				flow[cur][i]+=ret;
				flow[i][cur]-=ret;
				return ret;
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k>>d;
	for(int i=1;i<=d;i++){
		cin>>cap[bias+i][sink];
		adj[bias+i].push_back(sink);
		adj[sink].push_back(bias+i);
	}
	for(int i=1;i<=n;i++){
		int num;
		cin>>num;
		cap[src][i]=k;
		adj[src].push_back(i);
		adj[i].push_back(src);
		while(num--){
			int w;
			cin>>w;
			cap[i][bias+w]=1;
			adj[i].push_back(bias+w);
			adj[bias+w].push_back(i);
		}
	}
	while(f()){
		while(true){
			int ret=dfs(src,INF);
			if(ret==0){
				break;
			}
			result+=ret;
		}
	}
	cout<<result;
}

코드 제출 결과