Thursday, November 20, 2014

2013 KAIST ACM-ICPC 교내 대회 CLEANING 문제 풀이

알고스팟 문제 링크

Source Code


Mincost Maxflow 알고리즘으로 해결된다.

이분그래프를 구성하는데 좌변,우변에 1~n번째 점들을 배치한다.

i번째 점에서 x좌표 부호가 반대인 방향으로 (유량 = 1, 코스트 = 거리)로 엣지를 준다.

소스에는 왼쪽 부분그래프, 싱크에는 오른쪽 부분그래프에 (유량 = 1, 코스트 = 0)을 준다.

그리고 y축에 배치시키는 것을 왼쪽 부분그래프의 i번째 점에서 오른쪽 부분그래프의 i번째 점으로 (유량 = 1, 코스트 = 2*|X(i)|)로 준다.

MCMF를 돌린 후, Total Cost / 2을 답으로 정해주면 된다. 왜 나누기 2를 하냐하면, (a, b)가 짝이 된다면, 그 둘 사이의 거리가 2번 카운트 되기 때문이다. 현재 위치에서의 물건 개수와 선대칭 시킨 후 물건 개수가 같아야 하므로 대칭시켰을 때의 물건들과 현재 물건들과 항상 일대일 매칭 시킬 수 있음이 자명하므로 이 문제가 MCMF로 Polynomial한 시간에 풀린다고 할 수 있겠다.

No comments:

Post a Comment