디닉 알고리즘 &11406) 책 구매하기 2
지난번 hopcroft karp 알고리즘 (철자맞나?)에 대해 포스팅했다. 사실 maximum flow 문제에도 이와 굉장히 유사한 알고리즘이 있다. 바로 디닉 알고리즘이다.
최대 유량 문제에서 source node에서부터 시작하여 bfs를 통하여 각 node x가 모든 node에 대해 capacity가 남아있다면 남아있는 node y에 대하여 level[y] = level[x] + 1을 설정하여주면서 level을 갱신시켜준다.
이후 flow를 흘려보내는 dfs 과정에서도 hopcroft karp 알고리즘과 똑같이 level[y] = level[x] + 1 이고 cap[x][y] > 0 인 경우에만 dfs로 방문하는 과정을 거친다.
문제는 11406번 문제를 확인하면 되겠고, 코드는 아래에 첨부한다.
최대 유량 문제에서 source node에서부터 시작하여 bfs를 통하여 각 node x가 모든 node에 대해 capacity가 남아있다면 남아있는 node y에 대하여 level[y] = level[x] + 1을 설정하여주면서 level을 갱신시켜준다.
이후 flow를 흘려보내는 dfs 과정에서도 hopcroft karp 알고리즘과 똑같이 level[y] = level[x] + 1 이고 cap[x][y] > 0 인 경우에만 dfs로 방문하는 과정을 거친다.
문제는 11406번 문제를 확인하면 되겠고, 코드는 아래에 첨부한다.
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
|
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int c[205][205];
int level[205];
int N, M;
bool visited[205];
bool pos[205];
void bfs(){
queue<int> q;
for(int i=0; i<=M+N+1; i++) level[i] = -5;
level[0] = 0;
q.push(0);
while(!q.empty()){
int idx = q.front(); q.pop();
for(int i=0; i<=M+N+1; i++){
if(level[i] == -5 && c[idx][i] > 0){
level[i] = level[idx] + 1;
q.push(i);
}
}
}
}
int dfs(int p, int mn){
if(p == M+N+1) return mn;
if(!pos[p]) return pos[p];
int flow = 0;
for(int i=0; i<=M+N+1; i++){
if(level[i] == level[p] + 1 && c[p][i] > 0){
flow = dfs(i, min(mn, c[p][i]));
if(flow) {
c[p][i] -= flow;
c[i][p] += flow;
return flow;
}
}
}
return pos[p] = 0;
}
int main(){
scanf("%d%d", &N, &M);
for(int i=1; i<=N; i++) scanf("%d", &c[0][i]);
for(int i=N+1; i<=N+M; i++) scanf("%d", &c[i][N+M+1]);
for(int i=N+1; i<=N+M; i++){
for(int j=1; j<=N; j++){
scanf("%d", &c[j][i]);
}
}
int ans = 0;
while(1){
bfs();
for(int i=0; i<=M+N+1; i++) pos[i] = 1;
int flow = dfs(0, 99999999);
if(!flow) break;
ans += flow;
}
printf("%d", ans);
}
| cs |
댓글
댓글 쓰기