I. Pickup Game

ProblemI_Eng.pdf

이 문제는 전형적인 '가중치가 있는 이분매칭' 이다.

이러한 이분 매칭을 푸는데는 크게 두 가지 방법이 있다.

MCMF(Minimum cost & Maximum flow)와 헝가리안 메소드(Hungarian method) 가 있다.

필자는 헝가리안 메소드를 푼지 오래되어 이 문제를 MCMF로 해결했다. 이 문제에서는 두 매치 사이에 간선이 없는 경우가 있어서 헝가리안 메소드로 풀릴 수 있는지 헷갈릴 정도로 헝가리안 메소드에 대해 모른다.

MCMF가 다루는 그래프는 일반 maximum flow 문제에서 다루는 그래프와 사뭇 다르다.

maximum flow 에서 다루는 문제에서 그래프의 간선은 하나의 특성 값, 유량을 갖는다.

하지만 MCMF에서 다루는 그래프에서 간선은 두 개의 특성 값, 유량과 비용을 갖는다.

유량이 간선을 통과할 때 비용이 필요한 것이다. 간선의 비용이 cost고 그 간선을 지나는 유량 값이 flow일 때 그 간선의 총 비용은 flow*cost가 된다.

MCMF는 이러한 그래프에서 Maximum flow 중에 Minimum cost를 찾는 방법이다.

그래프에서 cost 값이 음수가 될 수 있으므로 cost 값의 부호를 뒤집어 Maximum cost 또한 구할 수 있다. (이는 헝가리안 메소드에서도 동일하다.)

이 문제는 최대 매칭 중에 최대 비용을 구하는 문제이므로 MCMF의 조건과 완벽히 동일한 전형적인 MCMF 문제이다.

MCMF는 간단하다. 우선, 비용이 cost인 간선의 역경로의 비용은 -cost 이다. Maximum flow 알고리즘에서 확대 경로를 구하는 과정에서 Bellman-ford를 이용하여 총 cost 값이 최소가 되는 확대 경로를 찾아 역경로를 만들어 주면 된다. 확대 경로가 나오지 않을 때까지 이를 반복하면 된다. 증명은 생략한다.

확대 경로를 Bellman-ford로 구하는 과정 중에 시간을 줄일 수 있는 유용한 방법이 있다. SPFA(Shortest Path Faster Algorithm)이라는 방법이다. 

source와 sink가 고정되어 있고 각 간선의 flow가 1이고 초기에 싸이클이 없는 그래프에서는 음수 싸이클이 생길 수가 없다.

I.cpp