글 읽기 - 이분매칭 포드포커슨알고리즘에 대하여..ㅠㅠ

temp 7년 전 0

혼자 이분매칭을 공부하고 있습니다.

그런데 정말 이해가 되지 않는 부분이 있어 질문을 드립니다.

요 이분매칭 소스에서

visited 배열과 backMatch 배열은 정확히 무얼 의미하나요?

처음에는 visited는 시작하는 집합으로생각했는데 소스보면 도착하는 녀석을 의미하는것 같기도하고..

backMatch는 전혀 모르겠습니다 ㅠㅠ

그리고 11번째줄과 12번째줄이 전혀 이해가 되지 않습니다. ㅠㅠ

무슨말인가요?

#define MAX_V 1000
vector<vector<int> > v(100);
int backMatch[MAX_V * 2 + 5];
bool visited[MAX_V * 2 + 5];

bool dfs(int now) {
	if (visited[now]) return false;
	visited[now] = true;
	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (backMatch[next] == -1 || dfs(backMatch[next])) {
			backMatch[next] = now;
			return true;
		}
	}
	return false;
}
int BipartiteMatching() {
	memset(backMatch, -1, sizeof(backMatch));
	int matched = 0;
	for (int i = 0; i < v.size(); i++) {
		memset(visited, false, sizeof(visited));
		if (dfs(i)) matched++;
	}
	return matched;
}

keh0711 7년 전 1

backMatch[next] ==-1는 아직 어떠한 정점과도 매칭되지 않았다는 것을 의미합니다.

만약 매칭이 되지 않았다면 backMatch[next]에는 현재 정점을 매칭시킵니다. backMatch[next]=now 요렇게

만약 backMatch[next] -1이 아니란 것은 이미 next가 다른 정점과 연결된 것을 의미합니다.

그래서 || dfs(backMatch[next])의 backMatch[next]는 next와 연결된 정점으로 가서 해당 정점이 next와 연결 외에도 다른 정점과 연결가능하다면 return true로 돌려주고 next는 now와 다시 맺어줍니다.

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

문제

문제

출처

ICPC

이분매칭 포드포커슨알고리즘에 대하여..ㅠㅠ

temp 7년 전 0

keh0711 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말