[BOJ 17412]

문제 바로가기 : https://www.acmicpc.net/problem/17412
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

나동빈님의 글을 참고했습니다. 감사합니다.

에드몬드 카프(Edmonds-Karp) 알고리즘으로 풀었다. 최대 유량을 구하는 기본 유형이다.
1번에서 2번으로 가는 최대 유량을 출력하면 되는데 간선별로 용량이 정해져 있지 않으므로 모두 1로 설정한다.
그리고 바로 에드몬드 카프 알고리즘을 적용해주면 끝나는데, 어떻게 동작하는지 처음에 이해하기가 조금 힘들었다.
설명은 위 링크에 잘 돼있으므로 전반적으로 어떻게 동작하는지를 중점적으로 적으려고 한다.

일단 cap[][]은 용량(capacity)을, flo[][]는 유량(flow)을, from[]은 어디서 왔는지를 의미한다.
그리고 함수 내에서 int형으로 선언된 flow는 ‘현재’ 얼마의 양이 지나갔는지를 의미한다.

기본적으로 BFS 형태를 취하며 BFS 안에서는 더 흘러갈 공간이 있을 때 + 지나간 적이 없을 때 값이 갱신된다.
여기서는 유량을 건들이지 않는다. 흘러갈 수 있는 경로를 설정해주는 단계이다.

queue<int> q;
q.push(start);
while (!q.empty()) {
	int cur = q.front();
	q.pop();
	for (auto& next : node[cur]) {
		if (cap[cur][next] - flo[cur][next] > 0 && from[next] == -1) {
			from[next] = cur;
			q.push(next);
			if (next == end) break;
		}
	}
}

//종료 조건
//더 이상 마지막으로 향하는 경로가 없음을 의미합니다
if (from[end] == -1) break;

위 부분을 지났다면 경로가 모두 설정된 상태다.
그럼 이렇게 설정된 경로상에서 발생할 수 있는 유량의 최댓값을 구한다.
처음에서 마지막으로 향하는 경로 중 제일 적은 용량이 곧 최대 유량이므로 이를 flow로 설정해준다.

int flow = INF;
for (int i = end; i != start; i = from[i]) {
	flow = min(flow, cap[from[i]][i] - flo[from[i]][i]);
}

위에서 구한 flow를 간선의 유량 정보를 나타내는 flo[][]에 갱신해준다.
반대 방향에서는 flow를 빼줘야 한다. 이 부분은 여기를 참고!
최종적으로 반환해야 하는 ret에 flow를 더해주고 다시 처음부터 반복한다.

for (int i = end; i != start; i = from[i]) {
	flo[from[i]][i] += flow;
	flo[i][from[i]] -= flow;
}

ret += flow;