[백준] 11405 책 구매하기 + Minimum Cost Maximum Flow

문제

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

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

이 온라인 서점은 책을 한권씩만 택배로 보낸다. 또, 택배비는 서점과 사람들 사이의 거리, 회원 등급등 여러 가지 요인에 따라 결정된다. 서점 i에서 사람 j에게 책을 한 권 보내는데 필요한 배송비는 Cij원이다. 모든 서점과 사람 사이의 배송비가 주어졌을 때, 각 사람이 책을 A1, A2, ..., AN권을 사는데 필요한 배송비의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 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이다. (1 ≤ Cij ≤ 1,000)

A1 + A2 + ... + AN은 B1 + B2 + ... + BM과 같다.

출력

첫째 줄에 배송비의 최솟값을 출력한다.

 

 

각 서점은 B(i)개의 책을 가지고 있고, 각 사람은 A(i)개의 책이 필요합니다.

소스에서 책을 한권씩 흘려보내면서 가장 적은 비용으로 모든 책을 흘려보내야 합니다.

MCMF 문제입니다

Minimum Cost Maximum Flow

에드몬드 카프 알고리즘과 다익스트라 알고리즘을 섞은듯한 느낌입니다.

카프알고리즘 처럼, 유량을 하나씩 흘려보낼텐데, 이때 큐를 사용해 비용이 가장 작은 곳으로 흘려보냅니다.

우선순위큐를 사용하는 다익스트라 알고리즘과는 조금 다릅니다.

 

수도코드는 다음과 같습니다.

나머지는 에드몬드 카프 알고리즘과 동일합니다.

#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, c[202][202], f[202][202], cost[202][202], S = 200, E = 201, INF = 987654321;
vi adj[202];
int parent[202], dist[202], inQ[202];
int main() {
    FAST;
    cin >> N >> M;
    // 정점 번호: 0~0+M: 서점, 100~100+N : 사람
    for (int i = 100; i < 100 + N; i++) {
        cin >> c[i][E];
        adj[i].push_back(E);
        adj[E].push_back(i);
    }
    for (int i = 0; i < M; i++) {
        cin >> c[S][i];
        adj[S].push_back(i);
        adj[i].push_back(S);
    }
    for (int i = 0; i < M; i++) {
        for (int j = 100; j < 100 + N; j++) {
            cin >> cost[i][j];
            cost[j][i] = -cost[i][j];
            c[i][j] = INF;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
    int ans = 0;
    while (1) {
        fill(parent, parent + 202, -1);
        fill(dist, dist + 202, INF);
        mset(inQ);
        queue<int>q;
        dist[S] = 0;
        inQ[S] = 1;
        q.push(S);
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            inQ[cur] = 0;
            for (auto next : adj[cur]) {
                if (c[cur][next] - f[cur][next] > 0 && dist[next] > dist[cur] + cost[cur][next]) {
                    dist[next] = dist[cur] + cost[cur][next];
                    parent[next] = cur;
                    if (!inQ[next]) {
                        q.push(next);
                        inQ[next] = 1;
                    }
                }
            }
        }
        if (parent[E] == -1) {
            break;
        }

        int flow = INF;
        //흐르는 최대 유량을 찾습니다.
        for (int i = E; i != S; i = parent[i]) {
            flow = min(flow, c[parent[i]][i] - f[parent[i]][i]);
        }
  		//실제로 흘려보냅니다.
        for (int i = E; i != S; i = parent[i]) {
            f[parent[i]][i] += flow;
            f[i][parent[i]] -= flow;
            ans += flow * cost[parent[i]][i];
        }
    }
    cout << ans;
  
}