티스토리 뷰
1. 문제 링크
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. 풀이
더 빠른속도로 푼 분들도 계셨다. 다른 방법으로도 풀어봐야겠다..
'알고리즘 > Network flow' 카테고리의 다른 글
boj, 백준) 2367. 파티 (C/C++) (0) | 2021.07.06 |
---|---|
boj, 백준) 11495. 격자 0 만들기 ( C / C++ ) (0) | 2021.04.24 |
boj, 백준) 17412. 도시 왕복하기1 (C/C++) (0) | 2021.04.07 |
백준, boj) 2316. 도시 왕복하기2 ( C / C++ ) (0) | 2020.03.29 |
boj, 백준) 11378. 열혈강호 4 ( C / C++ ) (0) | 2020.03.24 |
댓글