Bipartite Matching(이분 매칭), 열혈강호 시리즈

솔브닥 class 7에 있는 문제를 둘러보다가 열혈강호 시리즈를 풀게 되었다. 우선 이 시리즈는 Bipartite Matching을 사용하게 되는데, 간선 용량이 1인 Network Flow, Maximum Flow로 볼 수 있다.

이러한 문제는 일반적으로 Edmonds-Karp 알고리즘을 사용하는데, 이는 O(VE^2)에 작동한다. (Ford-Fulkerson 알고리즘도 있다. O(E+VF)에 작동한다. F: 최대 유량)

하지만 우리는 위의 문제를 DFS를 이용해 O(VE)에 해결할 수 있다.

$A$ -> $B$ 방향으로 매칭이 진행된다고 했을 때, $A$에서 $B$로 갈 때 이미 매칭이 된 상태인 부분이 있으면 해당 매칭에서의 $A$는 기존과 다른 $B$와 매칭을 시도한다. 매칭이 되지 않은 부분에 도달하면 해당 부분에서 매칭을 시킨다.

대략 이런 느낌으로 굴러간다.

bool dfs(int x) {
	for (int nx : v[x]) {
		if (!vst[nx]) {
			vst[nx] = 1;
			if (tasks[nx] == 0 || dfs(tasks[nx])) {
				tasks[nx] = x;
				return 1;
			}
		}
	}
	return 0;
}

// 다 매칭시켜본다.
for (int i = 1; i <= n; i++) {
	memset(vst, 0, sizeof vst);
	if (dfs(i)) cnt++;
}

열혈강호2: 바로 for분 내부에서 바로 한 번 더 매칭시켜보는 것으로 해결 가능하다.

열혈강호3: 한 번 매칭 후, 다시 처음부터 매칭시켜보면서 k를 줄여나가는 것으로 해결 가능하다.

03.20 동아리 스터디에서 선정된 문제에 열혈강호 6가 있었다. MCMF라 불리는 알고리즘을 사용해야 하는 문제였다. (비용 또한 있었기에) 열혈강호 5부터 풀면서 해당 알고리즘에 대해 감을 잡아보았다.

열혈강호5: 이분 매칭과 같이 그래프 모델링을 해주고, 시작점을 모든 직원과 연결해주고, 모든 일을 끝점에 연결해준 상태에서 진행하였다. 이때, 비용을 역방향으로 흘려주는 것도 잊지 않았다. 이후에는 SPFA와 SPFA에서 구한 비용을 가지고 Max Flow를 구하며 같이 곱해서 더해주면 답이 나온다.

열혈강호6: 열혈강호 6는 최대 비용을 구하는 것이므로, 열혈강호5에서 비용을 반전시켜주면 구할 수 있다.

나머지의 자세한 내용은 다음 주 스터디 정리본으로 작성할 예정이다. 네트워크 플로우를 공부하며 따라오는 여러 알고리즘들에 대해 공부를 할 수 있었다. 상당히 양이 많았다!