boj, 백준) 11407. 책 구매하기 3 (C/C++)

1. 문제 링크

www.acmicpc.net/problem/11407

11407번: 책 구매하기 3

 

2. 문제 개요

총 N명의 사람이 M개의 서점에서 책을 사려고 한다. 각 사람은 사려고 하는 책의 개수가 정해져 있고 서점도 팔 수 있는 책의 개수가 정해져 있다. i번째 서점에서 j번째 사람에게 C_ij개의 책을 팔 수 있고, 이때 택배로 보내는 비용이 D_ij라고 할 때, 책을 최대 몇 권 살 수 있는지, 그리고 이때의 배송비의 합의 최솟값을 구하는 프로그램을 작성.

 

3. 문제 힌트

MCMF (Minimum Cost Maximum Flow)문제.

책을 최대 몇 권 살 수 있는지는 유량이 최대일 때이고, 이때의 비용은 MCMF로 구할 수 있다.

 

간선에 가중치를 비용으로 두고, 스패닝 트리 구하는 것처럼 응용해서 구할 수 있다.

 

4. 문제 풀이

source -----> M개의 서점 --------> 사람들 --------> sink

로 네트워크를 모델링해서 문제를 풀 수 있다.

 

MCMF 알고리즘을 알고 있어야 한다.

MCMF 알고리즘은 다른 분들이 자세히 포스팅해놓으셨기 때문에 생략하고...

특별히 주의할 점은 기존 Network flow 문제와는 다르게 비용 정보가 존재하는데, flow에 역 flow를 주어 최대 유량을 구한다.

그래서 비용을 입력받을 때도 비용의 역비용이라고 해야 할까 [1][2] = 10 이면 [2][1] = -10으로 설정해주어야 한다는 것을 잊지 말자..

 

 

 

5. 코드

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

int n, m, ans_num, ans_cost;   //library : 0 ~ 99, person : 100 ~ 199
const int src = 200, sink = 201, bias = 100, INF = 987654321;
vector<int> adj[202];
int capacity[202][202], flow[202][202], cost[202][202];
int parent[202], dist[202];
bool inq[202];

void SPFA()
{
	queue<int> q;
	fill(parent, parent + 202, -1);
	fill(dist, dist + 202, INF);
	fill(inq, inq + 202, false);

	q.push(src);
	inq[src] = true;
	dist[src] = 0;

	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		inq[cur] = false;

		for (int next : adj[cur]) {

			if (dist[cur] + cost[cur][next] < dist[next] && capacity[cur][next] - flow[cur][next] > 0) {
				dist[next] = dist[cur] + cost[cur][next];
				parent[next] = cur;

				if (!inq[next]) {
					q.push(next);
					inq[next] = true;
				}
			}
		}
	}

	return;
}


void MCMF()
{
	while (1)
	{
		SPFA();
		if (parent[sink] == -1)
			break;
		int minflow = INF;

		for (int i = sink; i != src; i = parent[i])
			minflow = min(minflow, capacity[parent[i]][i] - flow[parent[i]][i]);

		for (int i = sink; i != src; i = parent[i]) {
			ans_cost += minflow * cost[parent[i]][i];
			flow[parent[i]][i] += minflow;
			flow[i][parent[i]] -= minflow;
		}
		ans_num += minflow;
	}
	return;
}


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

	//src --> library ---> person ---> sink

	for (int i = 0; i < n; ++i) {
		scanf("%d", &capacity[bias + i][sink]);
		adj[bias + i].push_back(sink);
		adj[sink].push_back(bias + i);
		//person(bias + i) ---> sink
	}

	for (int i = 0; i < m; ++i) {
		scanf("%d", &capacity[src][i]);
		adj[src].push_back(i);
		adj[i].push_back(src);
		//src -----> library (i)
	}
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j) {
			scanf("%d", &capacity[i][bias + j]);

			if (capacity[i][bias + j] != 0) {
				adj[i].push_back(bias + j);
				adj[bias + j].push_back(i);
			}
		}

	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j) {
			scanf("%d", &cost[i][bias + j]);
			cost[bias + j][i] = -cost[i][bias + j];
		}


	MCMF();

	printf("%d\n%d", ans_num, ans_cost);

	return 0;
}

 

6. 결과