pl0892029   10년 전

while( 경로가 존재하지 않을 때까지 ) {
     while( 큐가 빌 때까지 ) {
        for( 큐의 원소와 연결된 노드들을 순회 )
            if( 방문 안한 노드라면 )
                enqueue
    }
    if( 만족하는 경로가 존재할 때 ) {
        비용 추가
        경로와 비용 반대로
    }
}

이런 로직으로 이분 매칭과 MCMF를 풀었었는데요. 예선 문제 H번을 다음과 같이 풀면 시간초과가 나오더군요...

매치의 수는 노드의 수보다 작거나 같으므로, 노드의 수를 V, 간선의 수를 E라 하면 O(VE)가 나오지 않나요. ㅠ.ㅠ

더 빠른 방법이 존재하나요?

arine   10년 전

말씀하신 방법은 이분 매칭을 Edmonds-Karp algorithm으로 찾는 것입니다. 이 알고리즘에서 augment path(확장 경로)를 찾는 데 걸리는 시간은 O(VE)입니다. 그 이유는 각 edge가 critical인 경우가 최대 \(\frac{|V|}{2}\)번 있기 때문입니다. 이것에 대한 증명은 여기의 Lemma 2.9나 Introduction to Algorithm(CLRS)의 26.2절 정리 26.9를 참조하세요.
따라서 Edmonds-Karp algorithm의 시간복잡도는 \(O(VE^{2})\)이 됩니다.
더 빠른 알고리즘은 Dinic algorithm(\(O(V^{2}E)\))등이 있습니다. 그러나 보통 프로그래밍 대회에서는 Ford–Fulkerson이나 Edmonds-Karp로도 충분히 시간 내에 풀 수 있는 문제가 나옵니다.

이분 매칭의 경우 모든 간선의 capacity가 1이기 때문에 dfs를 쓰는 것이 평균적으로 더 빠르다고 알려져 있습니다. 코딩도 더 간단하게 할 수 있습니다. 첨부한 소스를 참고하세요.

pl0892029   10년 전

좋은 지식 감사합니다. 하나만 더 여쭈어보겠습니다. 지금까지 제가 쓰던 이 방식을 Ford-Fulkerson으로 알고 있었는데, dmonds-Karp algorithm과 Ford-Fulkerson algorithm은 어떻게 차이가 있는지 궁금합니다. ^^;

arine   10년 전

두 알고리즘의 차이점은 augment path를 찾는 방식의 차이입니다. 결론부터 말하자면 dfs를 사용해 경로를 찾는 것이 Ford-Fulkerson, bfs를 사용하는 것이 Edmonds-Karp입니다.
Edmonds-Karp의 경우 가능한 경로 중 최단경로(간선을 최소로 거치는 경로)를 찾습니다. 이것을 bfs의 optimal한 성질을 이용하여 구현하는 것입니다. (모든 간선의 가중치가 1 혹은 unit cost인 경우 최단경로를 bfs로 찾는 것과 같은 원리입니다. Flow network의 edge도 unit length를 가진다고 생각할 수 있기 때문입니다.)

myungwoo   10년 전

기본적인 이분매칭을 가장 빠르게 해결하는 알고리즘으로 Hopcroft-karp 알고리즘이 있습니다.
이 알고리즘 step 자체는 어렵지 않으나 시간 복잡도 계산이 어려워 사람들에게 생소한 알고리즘입니다.
http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
에서 의사코드를 보시면 이해하시기 편할겁니다.

시간복잡도는 random 그래프에서는 O(N)에 근접하고 최악에 O(E sqrt(V)) 이며, dense graph (꽉찬그래프)에서는 O(V^(2.5)) 입니다.
상당히 빠르죠!

h0ngjun7   10년 전

Ford-Fulkerson으로도 충분히 AC 받을 수 있습니다. linked-list나 STL의 vector 자료구조를 쓰시면 훨씬 빠르실 겁니다.

myungwoo   10년 전

@hongjun7
그건 확언할 수 없는게 출제진에서 어떤 알고리즘을 의도로 냈는지에 따라 달라지지.
실제로 Ford-Fulkerson에서 Augmented path를 구할 때 dfs를 쓰느냐 bfs를 쓰느냐는 차이가 확실히 나서...
Edmonds-Karp를 쓰는 것도 나쁘진 않을 듯..

h0ngjun7   10년 전

아 제목을 일반적인 질문으로 정정하셨구나..ㅠ

댓글을 작성하려면 로그인해야 합니다.