반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. MCMF

2. 그래프 모델링


그래프 모델링을 한 후 MCMF를 이용하면 정답을 구할 수 있기에 그래프 모델링에 집중해보자.


이 문제는 서점->사람으로 배달하는 과정이니

S-서점-사람-T라는 큰 틀로 그래프를 모델링 하려 한다.


1. 사람과 Sink를 연결해준다. 이때 각 사람이 사고싶어하는 개수에 맞게 Sink에 연결해준다.


2. Source와 서점을 연결해준다. 이때 각 서점이 팔수있는 개수에 맞게 Source를 연결해준다.


3. 이제 사람과 서점을 연결해준다. 

이때 입력받는 값들이 cost에 해당하므로 그에 해당하는 값들을 cost로 넣어주도록 한다.

capacity또한 입력받은 값을 이용하여 넣어준다.


이 과정을 마치고 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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#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 c[300][300];
 
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 cap;
            scanf("%d", &cap);
 
            c[i][j + m] = 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, c[i][j+m]);
        }
    }
 
    int result = 0;
    int cnt = 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;
 
        }
        cnt += flow;
    }
    printf("%d\n%d\n", cnt, result);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1495번] 기타리스트  (0) 2017.12.10
[3640번] 제독  (0) 2017.12.09
[8992번] 집기 게임  (0) 2017.12.07
[1544번] 사이클 단어  (0) 2017.12.07
[11405번] 책 구매하기  (0) 2017.12.06

티스토리툴바