boj, 백준) 11406. 책 구매하기 2 ( C/C++)

1. 문제 링크

www.acmicpc.net/problem/11406

11406번: 책 구매하기 2

2. 문제 개요

N명의 사람이 각자 A_j권의 책만큼 책을 구매하려고 한다.  서점은 M개가 있다. 서점에는 B_i권의 책이 있다.

사람 j가 서점 i에서 살 수 있는 최대 책의 개수는 C_ij이다.

이때, 사람들이 책을 가장 많이 사려고 할 때, 최대 몇 권까지 살 수 있는지 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

최대유량으로 풀 수 있을 것 같다.

사람이 살 수 있는 책의 개수를 source -> 사람으로 하고,

사람이 서점에서 살 수 있는 책의 최대 개수를 사람 -> 서점로 하자.

그리고 서점이 팔 수 있는 책의 최대 개수를 서점 -> sink로 정의하자.

 

 

4. 문제 풀이

모델을 

source ---(사려고하는 책의 개수)---> 사람 --------(해당 서점에서 살 수 있는 최대 책의 개수)-----> 서점 -----(서점에서 파는 책의 개수) ----> sink 

과 같이 정의하면 된다.

 

최대유량 알고리즘은 알고 있다고 가정하고, 

문제에서 주어진 내용들을 간선의 capacity, 용량으로 정의해주자.

그리고 용량이 존재하는 곳은 간선을 양방향으로 연결해주어야 증가 경로를 찾을 수 있다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
const int src = 200, sink = 201, bias = 100;
int n, m, ans;
int capacity[202][202], flow[202][202];
vector<int> adj[202];
 
void edmondKarp()
{
	while (1)
	{
		queue<int> q;
		q.push(src);
 
		int p[202];	//parent;
		fill(p, p + 202, -1);
 
		while (!q.empty()) {
			int cur = q.front(); q.pop();
 
			for (int next : adj[cur]) {
				if (capacity[cur][next] - flow[cur][next] > 0 && p[next] == -1) {
					q.push(next);
					p[next] = cur;
					if (next == sink)
						break;
				}
			}
		}
 
		//there is no augment path
		if (p[sink] == -1)
			break;
 
		int minflow = 987654321;
		for (int i = sink; i != src; i = p[i])
			minflow = min(minflow, capacity[p[i]][i] - flow[p[i]][i]);
 
		for (int i = sink; i != src; i = p[i]) {
			flow[p[i]][i] += minflow;
			flow[i][p[i]] -= minflow;
		}
		ans += minflow;
	}
}
int main()
{
	scanf("%d %d", &n, &m);
 
	for (int i = 0; i < n; ++i) {
		scanf("%d", &capacity[src][i]);
		adj[src].push_back(i);
		adj[i].push_back(src);
	}
	
	for (int i = 0; i < m; ++i) {
		scanf("%d", &capacity[bias + i][sink]);
		adj[bias + i].push_back(sink);
		adj[sink].push_back(bias + i);
	}
 
	for (int j = 0; j < m; ++j) 
		for (int i = 0; i < n; ++i) {
			scanf("%d", &capacity[i][bias + j]);
			adj[bias + j].push_back(i);
			adj[i].push_back(bias + j);
		}
	
	edmondKarp();
	
	printf("%d", ans);
 
	return 0;
}

 

6. 풀이

더  빠른속도로 푼 분들도 계셨다. 다른 방법으로도 풀어봐야겠다..