[11405번] 책 구매하기

문제 출처 :

https://www.acmicpc.net/problem/11405

알고리즘 분석 :

문제 해결에 필요한 사항

1. MCMF

2. 그래프 모델링

Source-서점-사람-Sink로 그래프 모델링을 준비한다.

1. 사람과 Sink를 연결한다. 이때 capacity는 입력받는 값으로 이용된다.(사람이 사고싶어하는 책의 개수를 의미)

2. Source와 서점을 연결한다. 이때 capacity는 입력받는 값으로 이용된다.(서점에서 가지고 있는 책의 개수를 의미)

3. 서점과 사람을 연결한다. 이때 cost는 입력받는 값을 이용하고 capacity = INF로 둔다.(어짜피 S-서점, 사람-T에서 결정나게 된다.)

이제 MCMF를 이용하면 결과를 구할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue>   using namespace std;   const int INF = 987654321; const int MAX_V = 300; const int S = MAX_V - 2; const int T = MAX_V - 1;   struct Edge {     int v, cost, capacity, flow, rev;     Edge(int v, int cost, int c, int f, int rev)         :v(v), cost(cost), capacity(c), flow(f), rev(rev) {} };   vector<Edge> adj[MAX_V];   void addEdge(int here, int next, int cost, int cap) {     adj[here].emplace_back(next, cost, cap, 0, adj[next].size());     adj[next].emplace_back(here, -cost, 0, 0, adj[here].size() - 1); }   int main() {     int n, m;     scanf("%d %d", &n, &m);       // 사람     for (int j = 1; j <= n; j++)     {         int cap;         scanf("%d", &cap);           addEdge(j + m, T, 0, cap);     }       // 서점     for (int i = 1; i <= m; i++)     {         int cap;         scanf("%d", &cap);           addEdge(S, i, 0, cap);     }       for (int i = 1; i <= m; i++)     {         for (int j = 1; j <= n; j++)         {             int cost;             scanf("%d", &cost);               addEdge(i, j + m, cost, INF);         }     }       int result = 0;       while (1)     {         int vPrev[MAX_V], ePrev[MAX_V], dist[MAX_V];         bool inQ[MAX_V] = { 0 };           queue<int> q;         fill(vPrev, vPrev + MAX_V, -1);         fill(ePrev, ePrev + MAX_V, -1);         fill(dist, dist + MAX_V, INF);           dist[S] = 0;         inQ[S] = true;           q.push(S);           while (!q.empty())         {             int here = q.front();             q.pop();               inQ[here] = false;               for (int i = 0; i < adj[here].size(); i++)             {                 int next = adj[here][i].v;                 int c = adj[here][i].capacity;                 int f = adj[here][i].flow;                 int d = adj[here][i].cost;                   if (c - f > 0 && dist[next] > dist[here] + d)                 {                     dist[next] = dist[here] + d;                     vPrev[next] = here;                     ePrev[next] = i;                       if (!inQ[next])                     {                         q.push(next);                         inQ[next] = true;                     }                 }             }         }         if (vPrev[T] == -1)             break;           int flow = INF;           for (int i = T; i != S; i = vPrev[i])         {             int prev = vPrev[i];             int idx = ePrev[i];             flow = min(flow, adj[prev][idx].capacity - adj[prev][idx].flow);         }           for (int i = T; i != S; i = vPrev[i])         {             int prev = vPrev[i];             int idx = ePrev[i];               result += adj[prev][idx].cost * flow;               adj[prev][idx].flow += flow;             adj[i][adj[prev][idx].rev].flow -= flow;           }     }     printf("%d\n", result);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus