최대유량 문제에서 정점 분할
·
PS/Algorithm
1. 정점이 용량을 갖는 유량 그래프최대유량 문제에서는 간선으로 용량 정보가 주어진다. 근데 만약 정점에 용량이 있다면? 음의 유량 처리 과정에 문제가 생긴다. 포드 풀커슨의 방법에서 가장 핵심적인 아이디어는 음의 유량을 만들어 기존 유량을 우회시키는 테크닉이다.정점 중심으로 생각해보면 정점 3은 나가는 방향의 간선 용량의 총합인 3의 용량을 갖는다고 할 수 있다. 1→3의 유량 2를 우회시키면 s-2-3-5-t에 2의 유량을 흘려보낼 수 있다. 여기서 유량 우회가 가능한 이유는 유량을 간선 정보로 관리하고 있기 때문이다. u-v 간선 용량을 capa[u][v], u-v 간선의 현재 유량을 flow[u][v] 라고 표현하면 그래프 자체에서 u와 v의 순서로 간선의 방향 정보를 모두 관리하고 있는 셈이다...