BOJ 2311 왕복 여행

mcmf로 풀 수 있는 문제이다.
1 -> N -> 1 에 소요되는 최소 시간을 구해야 하는데, 한 번 지나간 길은 다시 갈 수 없다.
한 번 지나간 길을 다시 갈 수 없다는 것을 각 길에 대해서 capacity를 1로 놓음으로써 해결할 수 있고, 왕복하는 것은 src->1->N->sink 에서 src->1, N->sink 의 capacity를 2로 놓음으로써 1에서 N까지 각 길을 한 번만 거치고 갈 수 있는 두 가지 경로를 구하는 것과 왕복하는 경로와 같다는 것을 이용해서 푼다. 정말 멋진 풀이다...

그런데, 양방향 간선인 점에서 좀 헷갈리는 부분이 있었다. 양방향 간선이므로 양방향으로 capacity를 1씩 주게 되는데, 그렇게 되면 한 번 지나간 길을 반대 방향으로 한 번 더 지나가게 될 수 있지 않을까? 라는 생각이 들었다.

오랜 고민 끝에, 그럴리 없다는 것을 알게 되었다. 바로 한 번 지나간 길(cost)의 반대 방향의 residual capacity는 1이되고 코스트는 -cost이다. 그렇기 때문에 capacity가 1이고 cost인 것을 선택하지 않고 -cost인 것을 선택하게 될 것이다.(mcmf에서는 bfs나 dfs가 아닌 최단 거리를 구하는 알고리즘으로 augment path를 찾기 때문에!) 즉, 만약 한 번 지나간 길의 반대 방향으로 한 번 더 지나가게 된다면 사실 그것은 한 번 더 지나가는 것이 아니라 상쇄하는 것이 된다. 즉, 그 길은 지나가지 않은 셈 치게 되는 것이다.

이 문제로 인해 좀 network flow에 대해 좀 더 이해할 수 있었다.

그리고 mcmf를 사용하지 않고도 풀 수 있는 방법이 있다. appa님이 질문게시판에 소개한 방법인데, 생각해보면 network flow의 원리와 비슷한 것 같기도 하고, 정말 멋있는 방법이다. 링크 -> https://www.acmicpc.net/board/view/8285
-1을 곱하는 것은 N에서 1로 가는 경로를 찾을 때, 어떤 길을 가지 않은 셈 치는, 즉 상쇄하는 효과를 주는 것 같다.

직접 예제를 가지고 해보면 이해가 더 빠르다.

내가 사용했던 예제
5 8
1 4 1
4 3 1
1 2 1
2 3 1
3 5 1
2 5 3
1 5 10
5 4 10

답은 7