반응형
문제 출처 :
https://www.acmicpc.net/problem/3980
알고리즘 분석 :
문제 해결에 필요한 사항
1. MCMF
2. 그래프 모델링
그래프 모델링을 다음과 같이 하고 MCMF를 이용하자.
1. Source와 사람간의 관계는 cost = 0, capacity = 1로 둔다.(사람을 1번만 이용가능하니)
2. 사람과 포지션의 관계를 생성한다. 이때 cost를 입력 받는데 0이면 그래프에 포함시키지 않고, 값이 존재하면 음수로 넣는다.
그 이유는 최상의 포지션을 만들어야 하기 때문이다.
3. 포지션과 Sink간의 관계는 cost = 0, capacity = 1로 둔다.(포지션도 1번만 이용가능하니)
이렇게 그래프 모델링을 완료하고 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 = 50; const int S = MAX_V - 2; const int T = MAX_V - 1; const int POSITION = 11; 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 tc; scanf("%d", &tc); while (tc--) { for (int i = 0; i < MAX_V; i++) adj[i].clear(); int result = 0; int cnt = 0; // Source와 사람간의 관계 for (int i = 1; i <= 11; i++) addEdge(S, i, 0, 1); // 포지션과 Sink의 관계 for (int i = 12; i <= 22; i++) addEdge(i, T, 0, 1); // 사람과 포지션 관계 for (int i = 1; i <= 11; i++) { for (int j = 12; j <= 22; j++) { int cost; scanf("%d", &cost); if (cost == 0) continue; addEdge(i, j, -cost, 1); } } 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; } cnt += flow; } printf("%d\n", -result); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[1544번] 사이클 단어 (0) | 2017.12.07 |
---|---|
[11405번] 책 구매하기 (0) | 2017.12.06 |
[11409번] 열혈강호 6 (0) | 2017.12.05 |
[7154번] Job Postings (0) | 2017.12.05 |
[11652번] 카드 (0) | 2017.12.04 |