Elevation

이분 그래프(bipartite graph)란 정점을 두 그룹($A, B$)로 나눴을 때, $A$와 $B$ 간에만 간선이 존재하고 그룹 내부에는 간선이 존재하지 않도록 만들 수 있는 그래프를 의미한다. 어떤 그래프가 이분 그래프인지 판별하는 방법은 간단하다. 탐색을 수행하면서 정점을 빨강/파랑으로 색칠해 주는데, 빨강색 정점에 인접한 정점은 모두 파란색으로 색칠되어야 하며, 파랑색 정점에 인접한 정점은 모두 빨간색으로 색칠되어야 한다. 그렇지 않으면 이분 그래프라고 볼 수 없다. 이분 매칭(bipartite matching)은 이분 그래프에서 최대 매칭을 찾는 알고리즘이다. 매칭(matching)은 정점을 공유하지 않도록 간선을 선택하는 방법이다. 정점의 입장에서는 최대 하나의 다른 정점과 연결되도록 하는..

MCMF최대 유량(플로우)의 심화 버전인 최소 비용 최대 유량 문제(Min-cost Max-flow, MCMF)에 대해 알아보자. 말 그대로 최대 유량을 흘리되, 사용하는 간선의 비용 합이 최소가 되도록 하는 문제이다. 최대 유량과 마찬가지로 이용 가능한(즉, $capacity - flow > 0$) 간선으로 이루어진 경로를 찾고, 흘릴 수 있는 최대 유량 $f$를 구하여, 정방향으로 유량 $f$를 흘리고 역방향으로 $-f$를 흘리는 것은 동일하다. 정방향과 역방향이 모두 정의되는 유량 $flow$와 달리, 용량 $capacity$의 경우 source → sink의 단방향으로만 정의함에 주의하여 구현하는 것 역시 동일하다. 차이점은 최소 비용의 경로를 찾아야 하기 때문에, 경로 탐색에 단순 bfs/dfs..