[백준] 11406 책 구매하기 2

문제

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

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

한 사람이 같은 서점에서 구매할 수 있는 책의 개수는 제한되어 있다. 사람 j가 서점 i에서 구매할 수 있는 책의 최대 개수는 Cij개이다. 모든 서점과 사람 사이의 구매 제한이 주어졌을 때, 책을 최대 몇 개 살 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 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)

출력

첫째 줄에 살 수 있는 책의 최대 개수를 출력한다.

 

 

#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 };

int N, M, V, S = 201, E = 202, c[203][203], f[203][203], ans;
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);
		}
	}
	while (1) {
		queue<int>q;
		int p[203];
		fill(p, p + 203, -1);
		q.push(S);
		while (!q.empty()) {
			auto r = q.front();
			q.pop();
			for (auto nxt : adj[r]) {
				if (c[r][nxt] - f[r][nxt] > 0 && p[nxt] == -1) {
					p[nxt] = r;
					q.push(nxt);
				}
			}
		}
		if (p[E] == -1)break;
		int flow = INT_MAX;
		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;
		}
	}
	cout << ans;
}

 

최대 유량 문제입니다.