PS 이야기

$O(N^2)$ Dynamic Programming 으로 풀린다.BOI 2009 beetle 문제와 매우 비슷한 문제이다. beetle 문제가 더 어렵고 이 문제는 더 간단하며, 다양한 풀이가 있을 것으로 예상된다. 우선 다이나믹 배열의 정의는 아래와 같다.L[i][j] = $p_i$ 부터 $p_j$까지 모두 방문했고 마지막 방문 지점이 $p_i$일 때 ($i

이 문제는 전형적인 '가중치가 있는 이분매칭' 이다.이러한 이분 매칭을 푸는데는 크게 두 가지 방법이 있다.MCMF(Minimum cost & Maximum flow)와 헝가리안 메소드(Hungarian method) 가 있다. 필자는 헝가리안 메소드를 푼지 오래되어 이 문제를 MCMF로 해결했다. 이 문제에서는 두 매치 사이에 간선이 없는 경우가 있어서 헝가리안 메소드로 풀릴 수 있는지 헷갈릴 정도로 헝가리안 메소드에 대해 모른다. MCMF가 다루는 그래프는 일반 maximum flow 문제에서 다루는 그래프와 사뭇 다르다.maximum flow 에서 다루는 문제에서 그래프의 간선은 하나의 특성 값, 유량을 갖는다.하지만 MCMF에서 다루는 그래프에서 간선은 두 개의 특성 값, 유량과 비용을 갖는다.유..

전형적인 이분매칭 문제다. 대회 끝나고, 단순히 '매칭'이라고만 들었을 때는 전혀 와닿지 않았고 해법이 떠오르질 않았다. 그래프를 어떻게 구성해야되는 것이며 그래프를 어떻게 구성해야되는 것이며... 머리 속이 복잡했다. 우선 이분 그래프의 양쪽에 0번 부터 $N-1$번까지 노드들을 총 $2N$개 만든다. i번 노드에서 j번 노드로 가는 방향성 에지가 있으면 이분그래프에서 왼쪽 i번 노드에서 오른쪽 j번 노드로 뻗는 간선을 그어준다.그 뒤 최대 매치수가 곧 답이다. 이 방법으로 답이 나오는 이유에 대한 자세한 설명은 생략한다. 포트퍼거슨으로 짜도 시간안에 나올 수 있다. 하지만, Hopcroft-karp 알고리즘을 통해 최악에 $O(M \sqrt{N})$의 시간복잡도로 풀 수 있으며, 평균 시간복잡도 $O..