말씀하신 방법은 이분 매칭을 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년 전
while( 큐가 빌 때까지 ) {
for( 큐의 원소와 연결된 노드들을 순회 )
if( 방문 안한 노드라면 )
enqueue
}
if( 만족하는 경로가 존재할 때 ) {
비용 추가
경로와 비용 반대로
}
}
이런 로직으로 이분 매칭과 MCMF를 풀었었는데요. 예선 문제 H번을 다음과 같이 풀면 시간초과가 나오더군요...
매치의 수는 노드의 수보다 작거나 같으므로, 노드의 수를 V, 간선의 수를 E라 하면 O(VE)가 나오지 않나요. ㅠ.ㅠ
더 빠른 방법이 존재하나요?