문제: icpc.me/11407
N명의 사람과 M개의 서점이 있을 때 각 사람들이 살 수 있는 책의 수와 각 서점이 파는 책의 개수 그리고 i번째 사람이 j번째 책을 살때의 비용과 살 수 있는 개수가 주어질 때 최대로 책을 사면서 비용을 최소로하는 경우의 살 수 있는 책의 개수와 비용을 출력하는 문제이다.
우리는 살 수 있는 책의 개수를 capacity로 비용을 cost로 그래프를 모델링 해준 뒤 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 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> #define INF 987654321 #define S 202 #define E 203 using namespace std; int n, m, x, a[102][102]; struct Edge { int v, cost, cap, rev; Edge(int v, int cost, int cap, int rev) :v(v), cost(cost), cap(cap), rev(rev) {} }; vector<vector<Edge>> vt; vector<int> pv, pe; void addEdge(int s, int e, int cost, int cap) { vt[s].emplace_back(e, cost, cap, vt[e].size()); vt[e].emplace_back(s, -cost, 0, vt[s].size() - 1); } bool spfa() { vector<int> v(E + 1, 0); vector<int> dist(E + 1, INF); queue<int> qu; qu.push(S); dist[S] = 0; v[S] = 1; while (qu.size()) { int here = qu.front(); v[here] = 0; qu.pop(); for (int i = 0; i < vt[here].size(); i++) { int there = vt[here][i].v; int cap = vt[here][i].cap; if (cap&&dist[there] > dist[here] + vt[here][i].cost) { dist[there] = dist[here] + vt[here][i].cost; pv[there] = here; pe[there] = i; if (!v[there]) { v[there] = 1; qu.push(there); } } } } return dist[E] != INF; } pair<int, int> solve() { pv.assign(E + 1, -1); pe.assign(E + 1, -1); int flow = 0, cost = 0; while (spfa()) { int minFlow = INF; for (int i = E; i != S; i = pv[i]) { int prev = pv[i]; int idx = pe[i]; minFlow = min(minFlow, vt[prev][idx].cap); } for (int i = E; i != S; i = pv[i]) { int prev = pv[i]; int idx = pe[i]; vt[prev][idx].cap -= minFlow; vt[i][vt[prev][idx].rev].cap += minFlow; cost += vt[prev][idx].cost*minFlow; } flow += minFlow; } return{ flow,cost }; } int main() { scanf("%d%d", &n, &m); vt.resize(E + 1); for (int i = 1; i <= n; i++) { scanf("%d", &x); addEdge(i + 100, E, 0, x); } for (int i = 1; i <= m; i++) { scanf("%d", &x); addEdge(S, i, 0, x); } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &x); addEdge(i, j + 100, x, a[i][j]); } } pair<int, int> r = solve(); printf("%d\n%d\n", r.first, r.second); return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)1585 경찰 (0) | 2017.03.11 |
---|---|
BOJ)4716 풍선 (0) | 2017.03.11 |
BOJ)14428 수열과 쿼리 16 (0) | 2017.03.09 |
BOJ)3640 제독 (0) | 2017.03.09 |
BOJ)11409 열혈강호 6 (0) | 2017.03.09 |