11495) 격자 0 만들기 & 디닉 알고리즘
옛날에 디닉 알고리즘에 관해 포스팅을 했었는데 코드가 잘못된 부분이 있었다...
그래서 디닉 알고리즘을 씀에도 불구하고 실행 시간이 느렸는데 그걸 어제 되어서야 깨달았다.
11495 격자 만들기 0 문제에서 중요한 것은 반드시 상하좌우로만 칸이 연결된다는 점이다.
이는 다시 말하면 대각선에 있는 요소들은 연결되지 않는다는 점이다.
그렇기 때문에
1 | 2
-----
3 | 4 라는 격자에 대해서
-> 1 - -> 2
S X -> E
-> 4 - -> 3
와 같은 모델링이 중요하다.
최대 유량 문제는 현재 주어진 문제를 모델링 할 수 있냐 없냐를 알아차리는 게 중요한 것 같다. 솔직히 말해서 다른 사람의 포스팅을 보지 못했으면 모델링 할 수 없었을 것 같다. ㅠ
암튼 이렇게 모델링이 되면
S와 1, 4 Node 사이에 격자에 적힌 숫자의 capacity를 준다.
2, 3 Node와 E 사이에 격자에 적힌 숫자의 capacity를 준다.
그외의 capacity는 INF를 준다.
디닉 알고리즘 구현에서 가장 중요한 것은 dfs에서 내가 이미 가능한지 가능하지 못한지 확인했던 Node를 표시하는 일이다.
(1) Node의 Edge를 이미 방문했을 경우를 레퍼런스를 이용해 표시
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int dfs(int cur, int flow) { if(cur == E) return flow; int cur_flow = 0; for(int &i = checked[cur]; i < adj[cur].size(); i++){ int next = adj[cur][i]; if(lv[next] == lv[cur] + 1 && c[cur][next] - f[cur][next] > 0) { cur_flow = dfs(next, min(flow, c[cur][next] - f[cur][next])); if(cur_flow) { f[cur][next] += cur_flow; f[next][cur] -= cur_flow; return cur_flow; } } } return 0; } | cs |
1 2 3 4 5 6 7 8 9 10 | long long flow = 0; while(bfs()) { for(int i=S; i<=E; i++) checked[i] = 0; while(1){ int cur_flow = dfs(S, INF); if(!cur_flow) break; flow += (long long)cur_flow; } } | cs |
Reference &i를 이용하면 i가 증가할 때마다 checked[cur]도 증가한다. 즉 다시 해당 current Node에 돌아오더라도 이미 방문했던 Node의 Edge는 방문하지 않는다.
2) Node가 모든 Edge를 이미 다 방문했을 경우 해당 Node를 방문하지 않음.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int dfs(int cur, int flow) { if(cur == E) return flow; int cur_flow = 0; for(auto next: adj[cur]) { if(!pos[next]) continue; if(lv[next] == lv[cur] + 1 && c[cur][next] - f[cur][next] > 0) { cur_flow = dfs(next, min(flow, c[cur][next] - f[cur][next])); if(cur_flow) { f[cur][next] += cur_flow; f[next][cur] -= cur_flow; return cur_flow; } } } return pos[cur] = 0; } | cs |
. pos라는 boolean array를 만들어서 더 짜낼 flow가 없으면 해당 node에 희망이 없음을 알린다. reference에 대한 명확한 이해가 없으면 2)가 구현하기에 쉽다.
하지만 1)이 더 빠르다.
댓글
댓글 쓰기