[백준] 11407 책 구매하기 3

문제

총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 서점도 1번부터 M번까지 번호가 매겨져 있으며, 각 서점이 가지고 있는 책의 개수는 B1, B2, ..., BM권 이다.

이 책을 사려고 하는 사람은 N명밖에 없으며, 서점에서 가지고 있는 책의 개수의 합과 사람들이 사려고 하는 책의 개수의 합은 같다.

한 사람이 같은 서점에서 구매할 수 있는 책의 개수는 제한되어 있다. 사람 j가 서점 i에서 구매할 수 있는 책의 최대 개수는 Cij개이다. 또, 온라인 서점은 책을 한권씩만 택배로 보낸다. 또, 택배비는 서점과 사람들 사이의 거리, 회원 등급등 여러 가지 요인에 따라 결정된다. 서점 i에서 사람 j에게 책을 한 권 보내는데 필요한 배송비는 Dij원이다.

모든 서점과 사람 사이의 구매 제한과 배송비가 주어졌을 때, 책을 최대 몇 개 살 수 있는지 그리고 그 때 배송비의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 온라인 서점의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

둘째 줄에는 각 사람이 사려고 하는 책의 개수 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100)

셋째 줄에는 각 온라인 서점이 가지고 있는 책의 개수 B1, B2, ..., BM이 주어진다. (1 ≤ Bi ≤ 100)

넷째 줄부터 M개의 줄에는 각 온라인 서점이 각 사람들에게 책을 최대 몇 권 팔 수 있는지를 나타내는 Cij가 주어진다. i번째 줄의 j번째 숫자는 온라인 서점 i에서 사람 j는 책을 최대 Cij권 살 수 있다는 의미이다. (0 ≤ Cij ≤ 100) 그 다음 줄부터 M개의 줄에는 각 온라인 서점이 각 사람들에게 책을 한 권 보내는데 필요한 배송비 Dij가 주어진다. i번째 줄의 j번째 숫자는 온라인 서점 i에서 사람 j에게 책을 한 권 보내는데 필요한 배송비 Dij이다. (1 ≤ Dij ≤ 1,000)

출력

첫째 줄에 살 수 있는 책의 최대 개수를 출력한다. 둘째 줄에는 책을 최대로 팔 때 배송비 합의 최솟값을 출력한다.

 

 

MCMF문제입니다.

최대유량최소비용 문제로, 가장 많이 책을 팔았을때, 가장 적은 배송비의 합을 구하는 문제입니다.

SPFA(shortest path faster algorithm)을 이용합니다. (음수 가중치가 존재할때 사용가능, 밸만포드와 비슷함)

SPFA는  책구매하기 문제에서 사용했었습니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

using namespace std;

typedef long long ll;
int N, M, f[203][203], c[203][203], d[203][203], S = 201, E = 202, ans, cost, INF = 98765431;
vi adj[203];
//서점 1~100
//사람 101~200
//소스 201
//싱크 202
int main() {
	FAST;
	cin >> N >> M;
	for (int i = 101; i <= 100 + N; i++) {
		cin >> c[i][E];
		adj[i].push_back(E);
		adj[E].push_back(i);
	}
	for (int i = 1; i <= M; i++) {
		cin >> c[S][i];
		adj[i].push_back(S);
		adj[S].push_back(i);
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 101; j <= 100 + N; j++) {
			cin >> c[i][j];
			adj[i].push_back(j);
			adj[j].push_back(i);
		}
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 101; j <= 100 + N; j++) {
			cin >> d[i][j];
			d[j][i] = -d[i][j];
		}
	}
	while (1) {
		queue<int>q;
		int p[203], dist[203], inQ[203];
		fill(dist, dist + 203, INF);
		mset(inQ);
		fill(p, p + 203, -1);
		q.push(S);
		dist[S] = 0;
		inQ[S] = 1;
		while (!q.empty()) {
			auto t= q.front();
			inQ[t] = 0;
			q.pop();
			for (auto r : adj[t]) {
				if (dist[r] > dist[t] + d[t][r] && c[t][r] - f[t][r] > 0) { //p[r]==-1?이 없음 밸만
					dist[r] = dist[t] + d[t][r];
					p[r] = t;
					if (!inQ[r]) {
						inQ[r] = 1;
						q.push(r);
					}
				}
			}
		}

		if (p[E] == -1)break;

		int flow = INF;
		for (int i = E; i != S; i = p[i]) {
			flow = min(flow, c[p[i]][i] - f[p[i]][i]);
		}
		ans += flow;
		

		for (int i = E; i != S; i = p[i]) {
			f[p[i]][i] += flow;
			f[i][p[i]] -= flow;
			cost += flow * d[p[i]][i];
		}
	}
	cout << ans << "\n" << cost;
}