책 구매하기
Problem link: https://www.acmicpc.net/problem/11405
전형적인 min-cost-max-flow 문제이다.
source
에서person_i
로 간선을 연결하는데, (source
,person_i
)의 capacity는person_i
가 구매를 희망하는 수량이다.
bookstore_j
에서sink
로 간선을 연결하는데, (bookstore_i
,sink
)의 capacity는bookstore_i
가 보유중인 수량이다.
persion_i
에서bookstore_j
로 간선을 연결하는데, 이때 (persion_i
,bookstore_j
)의 capacity는 무한, cost는 배송비로 한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int kMaxN = 100;
const int kMaxM = 100;
int N;
int M;
int COST[kMaxN + kMaxM + 2][kMaxN + kMaxM + 2];
int CAPA[kMaxN + kMaxM + 2][kMaxN + kMaxM + 2];
int FLOW[kMaxN + kMaxM + 2][kMaxN + kMaxM + 2];
int Spfa(vector<int>& prev)
{
prev.assign(N + M + 2, -1);
const int source = 0;
const int sink = N + M + 2 - 1;
vector<bool> queued(N + M + 2, false);
vector<int> distance(N + M + 2, (N + M + 2) * 1000 + 1);
queue<int> q;
q.push(source);
queued[source] = true;
distance[source] = 0;
while (!q.empty())
{
int here = q.front();
q.pop();
queued[here] = false;
for (int there = 0; there < N + M + 2; ++there)
{
int residual = CAPA[here][there] - FLOW[here][there];
if (residual > 0 && distance[there] > distance[here] + COST[here][there])
{
distance[there] = distance[here] + COST[here][there];
prev[there] = here;
if (!queued[there])
{
q.push(there);
queued[there] = true;
}
}
}
}
if (prev[sink] == -1)
{
return 0;
}
int flow = 100 * 100 + 1;
int cur = sink;
while (cur != source)
{
int residual = CAPA[prev[cur]][cur] - FLOW[prev[cur]][cur];
flow = min(flow, residual);
cur = prev[cur];
}
return flow;
}
int Solve(void)
{
int ret = 0;
const int source = 0;
const int sink = N + M + 2 - 1;
while (true)
{
vector<int> prev;
int flow = Spfa(prev);
if (flow == 0)
{
break;
}
int cur = sink;
while (cur != source)
{
ret += COST[prev[cur]][cur] * flow;
FLOW[prev[cur]][cur] += flow;
FLOW[cur][prev[cur]] -= flow;
cur = prev[cur];
}
}
return ret;
}
int main(void)
{
// For faster IO
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// Read input
cin >> N >> M;
const int source = 0;
const int sink = N + M + 2 - 1;
for (int it = 1; it < 1 + N; ++it)
{
int want;
cin >> want;
COST[source][it] = 0;
CAPA[source][it] = want;
FLOW[source][it] = 0;
FLOW[it][source] = 0;
}
for (int it = 1 + N; it < 1 + N + M; ++it)
{
int have;
cin >> have;
COST[it][sink] = 0;
CAPA[it][sink] = have;
FLOW[it][sink] = 0;
FLOW[sink][it] = 0;
}
for (int i = 1 + N; i < 1 + N + M; ++i)
{
for (int j = 1; j < 1 + N; ++j)
{
int cost;
cin >> cost;
COST[j][i] = cost;
COST[i][j] = -cost;
CAPA[j][i] = 100 * 100 + 1;
}
}
cout << Solve() << "\n";
return 0;
}
Author And Source
이 문제에 관하여(책 구매하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aram_father/책-구매하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)